科研之友
微信
新浪微博
Facebook
分享链接
摘要
A graph is (c(1), c(2), ... , c(k))-colorable if the vertex set can be partitioned into k sets V-1, V-2, ... , V-k, such that for every i : 1 %26lt;= i %26lt;= k the subgraph G[V-i] has maximum degree at most c(i). We show that every planar graph without 4- and 5-cycles is (1, 1, 0)-colorable. This is a relaxation of the Steinberg conjecture that every planar graph without 4- and 5-cycles are properly 3-colorable (i. e., (0, 0, 0)-colorable).
- 出版日期2013
