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


A relaxation of the strong Bordeaux Conjecture
Abstract:Let urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0001 be k nonnegative integers. A graph G is urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0002‐colorable if the vertex set can be partitioned into k sets urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0003, such that the subgraph urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0004, induced by urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0005, has maximum degree at most urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0006 for urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0007. Let urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0008 denote the family of plane graphs with neither adjacent 3‐cycles nor 5‐cycles. Borodin and Raspaud (2003) conjectured that each graph in urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0009 is (0, 0, 0)‐colorable (which was disproved very recently). In this article, we prove that each graph in urn:x-wiley:03649024:media:jgt22208:jgt22208-math-0010 is (1, 1, 0)‐colorable, which improves the results by Xu (2009) and Liu‐Li‐Yu (2016).
Keywords:planar graph  relaxed coloring  superextandable  strong bordeaux conjecture  05C10  05C15
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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