List-coloring the squares of planar graphs without 4-cycles and 5-cycles

DOI10.1002/JGT.22101zbMATH Open1368.05047arXiv1505.03197OpenAlexW2293855371MaRDI QIDQ4978441FDOQ4978441

Authors: Daniel W. Cranston, Bobby Jaeger 

Publication date: 10 August 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Let $G$ be a planar graph without 4-cycles and 5-cycles and with maximum degree $Deltage32$. We prove that $ch{i}_{ell}(G^2)leDelta+3$. For arbitrarily large maximum degree $Delta$, there exist planar graphs $G_{Delta}$ of girth 6 with $chi(G_{Delta}^2)=Delta+2$. Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to online list-coloring. In addition, we prove bounds for $L(p,q)$-labeling. Specifically, $lambd{a}_{2,1}(G)leDelta+8$ and, more generally, $lambd{a}_{p,q}(G)le(2q-1)Delta+6p-2q-2$, for positive integers $p$ and $q$ with $pgeq$. Again, these bounds come from a greedy coloring, so they immediately extend to the list-coloring and online list-coloring variants of this problem.

Full work available at URL: https://arxiv.org/abs/1505.03197

Recommendations

• List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles
• Degeneracy and colorings of squares of planar graphs without 4-cycles
• Labeling planar graphs without 4,5-cycles with a condition on distance two
• Coloring the square of a planar graph
• List-coloring the square of a subcubic graph

zbMATH Keywords

list coloringplanar graphsquare of a graph\(L(2,1)\)-labelingpaintability

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• List-coloring the square of a subcubic graph
• 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six and \(\varDelta \geq 18\)
• Coloring squares of planar graphs with girth six
• Labeling Planar Graphs with Conditions on Girth and Distance Two
• Coloring the square of a planar graph
• List Colouring Squares of Planar Graphs
• Coloring Powers of Planar Graphs
• Labeling planar graphs without 4,5-cycles with a condition on distance two

Cited In (7)

• List-coloring the square of a subcubic graph
• Degeneracy and colorings of squares of planar graphs without 4-cycles
• Painting squares in \(\Delta^2-1\) shades
• 2-distance coloring of planar graphs without 4-cycles and 5-cycles
• Coloring the square of maximal Planar graphs with diameter two
• List Colouring Squares of Planar Graphs
• List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles

This page was built for publication: List-coloring the squares of planar graphs without 4-cycles and 5-cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978441)