首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号