A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable

Miao Zhang, Min Chen () and Yiqiao Wang
Additional contact information
Miao Zhang: Zhejiang Normal University
Min Chen: Zhejiang Normal University
Yiqiao Wang: Beijing University of Chinese Medicine

Journal of Combinatorial Optimization, 2017, vol. 33, issue 3, No 3, 847-865

Abstract: Abstract A graph G is $$(d_1, d_2)$$ ( d 1 , d 2 ) -colorable if its vertices can be partitioned into subsets $$V_1$$ V 1 and $$V_2$$ V 2 such that in $$G[V_1]$$ G [ V 1 ] every vertex has degree at most $$d_1$$ d 1 and in $$G[V_2]$$ G [ V 2 ] every vertex has degree at most $$d_2$$ d 2 . Let $$\mathcal {G}_5$$ G 5 denote the family of planar graphs with minimum cycle length at least 5. It is known that every graph in $$\mathcal {G}_5$$ G 5 is $$(d_1, d_2)$$ ( d 1 , d 2 ) -colorable, where $$(d_1, d_2)\in \{(2,6), (3,5),(4,4)\}$$ ( d 1 , d 2 ) ∈ { ( 2 , 6 ) , ( 3 , 5 ) , ( 4 , 4 ) } . We still do not know even if there is a finite positive d such that every graph in $$\mathcal {G}_5$$ G 5 is (1, d)-colorable. In this paper, we prove that every graph in $$\mathcal {G}_5$$ G 5 without adjacent 5-cycles is (1, 7)-colorable. This is a partial positive answer to a problem proposed by Choi and Raspaud that is every graph in $$\mathcal {G}_5\;(1, 7)$$ G 5 ( 1 , 7 ) -colorable?.

Keywords: Planar graphs; Improper coloring; Discharging method (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0010-3 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:33:y:2017:i:3:d:10.1007_s10878-016-0010-3

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

DOI: 10.1007/s10878-016-0010-3

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 ().