|
Sibirskii Matematicheskii Zhurnal, 2011, Volume 52, Number 1, Pages 30–38
(Mi smj2175)
|
|
|
|
This article is cited in 17 scientific papers (total in 17 papers)
Injective $(\Delta+1)$-coloring of planar graphs with girth 6
O. V. Borodina, A. O. Ivanovab a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Institute for Mathematics and Informatics, Yakutsk State University, Yakutsk
Abstract:
A vertex coloring of a graph $G$ is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number $\chi_i(G)$ of the colors required for an injective coloring of a graph $G$ is clearly not less than the maximum degree $\Delta(G)$ of $G$. There exist planar graphs with girth $g\ge6$ and $\chi_i=\Delta+1$ for any $\Delta\ge2$. We prove that every planar graph with $\Delta\ge18$ and $g\ge6$ has $\chi_i\le\Delta+1$.
Keywords:
planar graph, injective coloring, girth.
Received: 03.02.2010
Citation:
O. V. Borodin, A. O. Ivanova, “Injective $(\Delta+1)$-coloring of planar graphs with girth 6”, Sibirsk. Mat. Zh., 52:1 (2011), 30–38; Siberian Math. J., 52:1 (2011), 23–29
Linking options:
https://www.mathnet.ru/eng/smj2175 https://www.mathnet.ru/eng/smj/v52/i1/p30
|
|