RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2011 Volume 52, Number 1, Pages 30–38 (Mi smj2175)

This article is cited 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.

UDC: 519.17

Received: 03.02.2010


 English version:
Siberian Mathematical Journal, 2011, 52:1, 23–29

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024