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


Maximum average degree and relaxed coloring
Authors:Michael Kopreski  Gexin Yu
Affiliation:Department of Mathematics, The College of William and Mary, Williamsburg, VA, 23185, USA
Abstract:We say a graph is (d,d,,d,0,,0)-colorable with a of d’s and b of 0’s if V(G) may be partitioned into b independent sets O1,O2,,Ob and a sets D1,D2,,Da whose induced graphs have maximum degree at most d. The maximum average degree, mad(G), of a graph G is the maximum average degree over all subgraphs of G. In this note, for nonnegative integers a,b, we show that if mad(G)<43a+b, then G is (11,12,,1a,01,,0b)-colorable.
Keywords:Relaxed coloring  Maximum average degree  Global discharging
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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