20.500.12556/DiRROS-18637 Injective coloring of graphs revisited 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. two-step graph of a graph injective coloring open packing hypercubes dvostopenjski graf grafa injektivno barvanje odprto pakiranje hiperkocke true false true Angleški jezik Slovenski jezik Neznano 2024-04-09 09:08:31 2024-04-09 09:08:31 2024-04-10 03:38:21 0000-00-00 00:00:00 2023 0 0 art. 113348 (12 str.) iss. 5 Vol. 346 May 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2023-05-01 519.17 0012-365X 10.1016/j.disc.2023.113348 141111555 1-s2.0-S0012365X23000341-main.pdf 1-s2.0-S0012365X23000341-main.pdf 1 6E8358E6F504EA4CDB807E1BC77D0BBF 55771cd94b6f68423818c9cd76e336fb14134f77a848fd78a6d246383692e224 f08cf485-f630-11ee-ae20-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25447 https://www.sciencedirect.com/science/article/pii/S0012365X23000341 1 361e5237-f62f-11ee-ae20-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25446 Inštitut za matematiko, fiziko in mehaniko 0 0 0