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

Diskretn. Anal. Issled. Oper., 2009 Volume 16, Issue 2, Pages 16–20 (Mi da565)

This article is cited in 18 papers

Near-proper vertex 2-colorings of sparse graphs

O. V. Borodina, A. O. Ivanovab

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Institute of Mathematics at Yakutsk State University, Yakutsk, Russia

Abstract: A graph $G$ is $(2,1)$-colorable if its vertices can be partitioned into subsets $V_1$ and $V_2$ such that in $G[V_1]$ any component contains at most two vertices while $G[V_2]$ is edgeless. We prove that every graph $G$ with the maximum average degree $\mathrm{mad}(G)$ smaller than 7/3 is $(2,1)$-colorable. It follows that every planar graph with girth at least 14 is $(2,1)$-colorable. We also construct a planar graph $G_n$ with $\mathrm{mad}(G_n)=(18n-2)/(7n-1)$ that is not $(2,1)$-colorable. Bibl. 5.

Keywords: planar graph, girth, coloring, partition.

UDC: 519.172.2

Received: 09.02.2008


 English version:
Journal of Applied and Industrial Mathematics, 2010, 4:1, 21–23

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024