RT journal article
T1 Injective coloring of graphs revisited
A1 Brešar, Boštjan
A1 Samadi, Babak
A1 González Yero, Ismael
A2 Matemáticas
K1 Hypercube
K1 Injective coloring
K1 Open packing
K1 Two-step graph of a graph
AB 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 χ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 χi(G)≥[Formula presented] holds for any connected graph G of order n≥2, size m, and the open packing number ρo, and characterize the class of graphs attaining the bound. Regarding the well known bound χi(G)≥Δ(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 χ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.
PB Elsevier
SN 0012-365X
YR 2023
FD 2023-02-02
LK http://hdl.handle.net/10498/29437
UL http://hdl.handle.net/10498/29437
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 12-nov-2026