Every planar graph with cycles of length neither 4 nor 5 is $$(1,1,0)$$ -colorable

Lingji Xu (), Zhengke Miao () and Yingqian Wang ()
Additional contact information
Lingji Xu: Zhejiang Normal University
Zhengke Miao: Jiangsu Normal University
Yingqian Wang: Zhejiang Normal University

Journal of Combinatorial Optimization, 2014, vol. 28, issue 4, No 5, 774-786

Abstract: Abstract Let $$d_1, d_2,\dots ,d_k$$ be $$k$$ non-negative integers. A graph $$G$$ is $$(d_1,d_2,\ldots ,d_k)$$ -colorable, if the vertex set of $$G$$ can be partitioned into subsets $$V_1,V_2,\ldots ,V_k$$ such that the subgraph $$G[V_i]$$ induced by $$V_i$$ has maximum degree at most $$d_i$$ for $$i=1,2,\ldots ,k.$$ Let $$\digamma $$ be the family of planar graphs with cycles of length neither 4 nor 5. Steinberg conjectured that every graph of $$\digamma $$ is $$(0,0,0)$$ -colorable. In this paper, we prove that every graph of $$\digamma $$ is $$(1,1,0)$$ -colorable.

Keywords: Planar graph; Steinberg’s conjecture; Improper coloring (search for similar items in EconPapers)
Date: 2014
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-012-9586-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:28:y:2014:i:4:d:10.1007_s10878-012-9586-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-012-9586-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().