EN|RU 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 © Sobolev Institute of Mathematics, 2015