Degeneracy and Colorings of Squares of Planar Graphs without 4-Cycles
| Autor: | Théo Pierron, Ilkyoo Choi, Daniel W. Cranston |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematics::Combinatorics
010102 general mathematics Degenerate energy levels 0102 computer and information sciences 01 natural sciences Degeneracy (graph theory) Upper and lower bounds Graph Planar graph Combinatorics Computational Mathematics symbols.namesake 05C15 010201 computation theory & mathematics FOS: Mathematics symbols Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) Chromatic scale 0101 mathematics Mathematics |
| Zdroj: | Combinatorica. 40:625-653 |
| ISSN: | 1439-6912 0209-9683 |
| Popis: | 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$. Comment: 24 pages, 6 figures; revised version incorporates suggestions of referees; to appear in Combinatorica |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink