Paper Info
Title
Every planar graph without triangles adjacent to cycles of length 3 or 6 is (1,1,1)-colorable
Abstract
Let c1,c2,…,ck be non-negative integers. A graph G is (c1,c2,…,ck)-colorable if the vertex set of G can be partitioned into k sets V1,V2,…,Vk, such that G[Vi], the subgraph induced by Vi, has maximum degree at most ci for i∈[k]. Wang and Xu (2015) posed some open problems, one of which is that every planar graph without adjacent triangles is (1,1,1)-colorable. In this paper, we prove that every planar graph without triangles adjacent to cycles of length 3 or 6 is (1,1,1)-colorable.
Year
DOI
Venue
2020
10.1016/j.disc.2020.111846
Discrete Mathematics
Keywords
DocType
Volume
Planar graph,Bad cycle,Superextension,Discharging
Journal
343
Issue
ISSN
Citations 
6
0012-365X
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Ziwen Huang101.69