Journal
COMBINATORICA
Volume 40, Issue 5, Pages 625-653Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s00493-019-4014-3
Keywords
05C15
Categories
Funding
- Basic Science Research Program through the National Research Foundation of Korea (NRF) - Ministry of Education [NRF-2018R1D1A1B07043049]
- Hankuk University of Foreign Studies Research Fund
- NSA [H98230-15-1-0013]
Ask authors/readers for more resources
We prove several results on coloring squares of planar graphs without 4-cycles. First, we show that ifGis such a graph, thenG(2)is (Delta(G) + 72)-degenerate. This implies an upper bound of Delta(G) divide 73 on the chromatic number ofG(2)as well as on several variants of the chromatic number such as the list-chromatic number, paint number, Alon-Tarsi number, and correspondence chromatic number. We also show that if Delta(G) is sufficiently large, then the upper bounds on each of these parameters ofG(2)can all be lowered to Delta(G) + 2 (which is best possible). To complement these results, we show that 4-cycles are unique in having this property. Specifically, let S be a finite list of positive integers, with 4 is not an element of S. For each constantC, we construct a planar graphG(s,c)with no cycle with length inS, but for which chi(GS,C2) >Delta(G(s,c)) +C.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available