RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2010 Volume 17, Issue 5, Pages 22–36 (Mi da622)

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

UDC: 519.17

Received: 02.02.2010
Revised: 28.07.2010



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024