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

DOI10.1002/JGT.22101MaRDI QIDQ4978441zbMATH OpenOpenAlexFDO

Authors Daniel W. Cranston, Bobby Jaeger

Publication date 10 August 2017

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

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

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)

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.

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

Cites work

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

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 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles
• List Colouring Squares of Planar Graphs

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)