|
Diskretnyi Analiz i Issledovanie Operatsii, 2010, Volume 17, Issue 5, Pages 22–36
(Mi da622)
|
|
|
|
This article is cited in 13 scientific papers (total in 13 papers)
List 2-distance $(\Delta+1)$-coloring of planar graphs with girth at least 7
A. O. Ivanova Institute of Mathematics at Yakutsk State University, Yakutsk, Russia
Abstract:
A trivial lower bound for the 2-distance chromatic number $\chi_2(G)$ of every graph $G$ with maximum degree $\Delta$ is $\Delta+1$. There are graphs with arbitrarily large $\Delta$ and girth $g\le6$ having $\chi_2(G)\ge\Delta+2$. In the paper are improved previously known restrictions on $\Delta$ and $g$ under which every planar graph $G$ has $\chi_2(G)=\Delta+1$. Ill. 2, bibliogr. 24.
Keywords:
planar graph, 2-distance coloring, list coloring.
Received: 02.02.2010 Revised: 28.07.2010
Citation:
A. O. Ivanova, “List 2-distance $(\Delta+1)$-coloring of planar graphs with girth at least 7”, Diskretn. Anal. Issled. Oper., 17:5 (2010), 22–36
Linking options:
https://www.mathnet.ru/eng/da622 https://www.mathnet.ru/eng/da/v17/i5/p22
|
Statistics & downloads: |
Abstract page: | 499 | Full-text PDF : | 98 | References: | 51 | First page: | 5 |
|