Volume 16, No 2, 2009, P. 16-20
UDC 519.172.2
O. V. Borodin, A. O. Ivanova
Near-proper vertex 2-colorings of sparse graphs
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.
Borodin Oleg Veniaminovich 1
Ivanova Anna Olegovna 2
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2.
Institute of Mathematics at Yakutsk State University,
677891 Yakutsk, Russia
e-mail: brdnoleg@math.nsc.ru, shmgnanna@mail.ru
