Near-proper vertex 2-colorings of sparse graphs |
| |
Authors: | O V Borodin A O Ivanova |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk,Russia;2.Institute of Mathematics,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 each component in GV
1] contains at most two vertices while GV
2] is edgeless. We prove that every graph with maximum average degree mad(G) < 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 mad (G
n
) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|