Injective coloring of graphs revisited

Boštjan Brešar (Author), Babak Samadi (Author), Ismael G. Yero (Author)

Abstract

Odprto pakiranje grafa ▫$G$▫ je taka množica ▫$S$▫ vozlišč grafa ▫$G$▫, da nobeni dve vozlišči iz ▫$S$▫ nimata skupnega soseda v ▫$G$▫. Injektivno kromatično število ▫$\chi_i(G)$▫ grafa ▫$G$▫ je najmanjše število barv, ki jih vozliščem grafa ▫$G$▫ lahko priredimo tako, da je vsak barvni razred odprto pakiranje. Ekvivalentna definicija pravi, da je injektivno kromatično število grafa ▫$G$▫ enako kromatičnemu številu t.i. dvostopenjskega grafa grafa ▫$G$▫, ki je graf z isto množico vozlišč kot graf ▫$G$▫, v katerem sta dva vozlišči sosedni, če imata v grafu ▫$G$▫ kako skupno sosedo. Koncept injektivnega barvanja so raziskovali mnogi avtorji, v tem članku pa pogledamo nanj z dveh novih perspektiv, povezanih z odprtimi pakiranji ter operacijo dvostopenjskega grafa. Dokažemo več splošnih mej za injektivno kromatično število, izraženih s številom odprtega pakiranja. Med drugim dokažemo, da velja ▫$\chi_i(G) \ge \frac{1}{2}\sqrt{\frac{1}{4}+\frac{2m-n}{\rho^{o}}}$▫, kjer je ▫$G$▫ poljuben povezan graf, reda ▫$n\ge 2$▫, s številom povezav ▫$m$▫ in številom odprtega pakiranja ▫${\rho^{o}}$▫ in ob tem še okarakteriziramo razred grafov, ki to mejo dosežejo. V povezavi z dobro poznano mejo ▫$\chi_i(G)\ge \Delta(G)$▫, opišemo družino ekstremalnih grafov in dokažemo, da je problem odločitve, ali velja enakost v tej meji NP-poln problem (celo znotraj regularnih grafov), s čimer rešimo odprt problem, zastavljen v enem od prejšnjih člankov o injektivnih barvanjih. Nadalje obravnavamo tudi kromatično število dvostopenjskega grafa poljubnega grafa in ga primerjamo s kličnim številom in maksimalno stopnjo grafa. Predstavimo dve veliki družini grafov, za katere je ▫$\chi_i(G)$▫ enak kardinalnosti največje klike dvostopenjskega grafa grafa ▫$G$▫. Nazadnje obravnavamo še grafe, ki premorejo injektivno barvanje, v katerem so vsi barvni razredi maksimalna odprta pakiranja. Okarakteriziramo tri podrazrede tega razreda grafov med grafi s premerom 2 in najdemo delno karakterizacijo hiperkock s to lastnostjo.

Keywords

dvostopenjski graf grafa;injektivno barvanje;odprto pakiranje;hiperkocke;two-step graph of a graph;injective coloring;open packing;hypercubes;

Data

Language:	English
Year of publishing:	2023
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	141111555
ISSN:	0012-365X
Views:	16
Downloads:	6
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	Slovenian
Secondary title:	Nov vpogled v injektivna barvanja grafov
Secondary abstract:	An open packing in a graph ▫$G$▫ is a set ▫$S$▫ of vertices in ▫$G$▫ such that no two vertices in ▫$S$▫ have a common neighbor in ▫$G$▫. The injective chromatic number ▫$\chi_i(G)$▫ of ▫$G$▫ is the smallest number of colors assigned to vertices of ▫$G$▫ such that each color class is an open packing. Alternatively, the injective chromatic number of ▫$G$▫ is the chromatic number of the two-step graph of ▫$G$▫, which is the graph with the same vertex set as ▫$G$▫ in which two vertices are adjacent if they have a common neighbor. The concept of injective coloring has been studied by many authors, while in the present paper we approach it from two novel perspectives, related to open packings and the two-step graph operation. We prove several general bounds on the injective chromatic number expressed in terms of the open packing number. In particular, we prove that ▫$\chi_i(G) \ge \frac{1}{2}\sqrt{\frac{1}{4}+\frac{2m-n}{\rho^{o}}}$▫ holds for any connected graph ▫$G$▫ of order ▫$n\ge 2$▫, size ▫$m$▫, and the open packing number ▫${\rho^{o}}$▫, and characterize the class of graphs attaining the bound. Regarding the well known bound ▫$\chi_i(G)\ge \Delta(G)$▫, we describe the family of extremal graphs and prove that deciding when the equality holds (even for regular graphs) is NP-complete, solving an open problem from an earlier paper. Next, we consider the chromatic number of the two-step graph of a graph, and compare it with the clique number and the maximum degree of the graph. We present two large families of graphs in which $\chi_i(G)$ equals the cardinality of a largest clique of the two-step graph of ▫$G$▫. Finally, we consider classes of graphs that admit an injective coloring in which all color classes are maximal open packings. We give characterizations of three subclasses of these graphs among graphs with diameter 2, and find a partial characterization of hypercubes with this property.
Secondary keywords:	dvostopenjski graf grafa;injektivno barvanje;odprto pakiranje;hiperkocke;
Pages:	art. 113348 (12 str.)
Volume:	ǂVol. ǂ346
Issue:	ǂiss. ǂ5
Chronology:	May 2023
DOI:	10.1016/j.disc.2023.113348
ID:	23384970