Back to Search
Start Over
Degeneracy and Colorings of Squares of Planar Graphs without 4-Cycles
- Source :
- Combinatorica. Vol. 40(5), 2020, pp. 625-653
- Publication Year :
- 2018
-
Abstract
- We prove several results on coloring squares of planar graphs without 4-cycles. First, we show that if $G$ is such a graph, then $G^2$ is $(\Delta(G)+72)$-degenerate. This implies an upper bound of $\Delta(G)+73$ on the chromatic number of $G^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 of $G^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\notin S$. For each constant $C$, we construct a planar graph $G_{S,C}$ with no cycle with length in $S$, but for which $\chi(G_{S,C}^2) > \Delta(G_{S,C})+C$.<br />Comment: 24 pages, 6 figures; revised version incorporates suggestions of referees; to appear in Combinatorica
- Subjects :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Journal :
- Combinatorica. Vol. 40(5), 2020, pp. 625-653
- Publication Type :
- Report
- Accession number :
- edsarx.1806.07204
- Document Type :
- Working Paper