2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4

DOI10.1016/J.DISC.2023.113405MaRDI QIDQ6041534zbMATH OpenOpenAlexWikidataFDO

Authors Hoang La, Kenny Štorgel

Publication date 31 May 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

distance coloringexact square coloringinjective coloringlist coloringplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: In the past various distance based colorings on planar graphs were introduced. We turn our focus to three of them, namely $2$-distance coloring, injective coloring, and exact square coloring. A $2$-distance coloring is a proper coloring of the vertices in which no two vertices at distance $2$ receive the same color, an injective coloring is a coloring of the vertices in which no two vertices with a common neighbor receive the same color, and an exact square coloring is a coloring of the vertices in which no two vertices at distance exactly $2$ receive the same color. We prove that planar graphs with maximum degree $Delta=4$ and girth at least $4$ are $2$-distance list $(Delta+7)$-colorable and injectively list $(Delta+5)$-colorable. Additionally, we prove that planar graphs with $Delta=4$ are injectively list $(Delta+7)$-colorable and exact square list $(Delta+6)$-colorable.

Recommendations

• List 2-distance coloring of planar graphs with maximal degree less than 5
• scientific article; zbMATH DE number 6004909
• List 2-distance coloring of planar graphs
• List 2-distance \(\varDelta +3\)-coloring of planar graphs without 4,5-cycles
• 2-distance list ( +2)-coloring of planar graphs with girth at least 10
• scientific article; zbMATH DE number 6135423
• scientific article; zbMATH DE number 5875579
• List 2-distance \((\varDelta +2)\)-coloring of planar graphs with girth six
• Coloring the square of maximal Planar graphs with diameter two
• A new result of list 2-distance coloring of planar graphs with g(G) 5

Cites work

• 2-distance list ( +2)-coloring of planar graphs with girth at least 10
• 2-distance list \((\varDelta +3)\)-coloring of sparse graphs
• \(2\)-distance coloring of planar graphs with maximum degree \(5\)
• Choosability of the square of planar subcubic graphs with large girth
• Chromatic numbers of exact distance graphs
• Coloring the square of a \(K_{4}\)-minor free graph
• Colouring exact distance graphs of chordal graphs
• Counterexamples to a conjecture on injective colorings
• Distance-two colourings of Barnette graphs
• Exact distance colouring in trees
• Exact square coloring of subcubic planar graphs
• scientific article; zbMATH DE number 3834025 (Why is no real title available?)
• scientific article; zbMATH DE number 3265667 (Why is no real title available?)
• scientific article; zbMATH DE number 3308991 (Why is no real title available?)
• Improved square coloring of planar graphs
• Injective choosability of subcubic planar graphs with girth 6
• Injective coloring of planar graphs
• Injective coloring of planar graphs with girth 6
• Injective coloring of planar graphs with girth 7
• Injective coloring of plane graphs with girth 5
• Injective colorings of graphs with low average degree
• Injective colorings of planar graphs with few colors
• Injective colorings of sparse graphs
• List 2-facial 5-colorability of plane graphs with girth at least 12
• List injective coloring of a class of planar graphs without short cycles
• List injective coloring of planar graphs with girth 5, 6, 8
• List injective colorings of planar graphs
• On the injective chromatic number of graphs
• Painting squares in \(\Delta^2-1\) shades
• Some bounds on the injective chromatic number of graphs
• Some results on the injective chromatic number of graphs
• Sparsity. Graphs, structures, and algorithms
• The square of a planar cubic graph is 7-colorable
• Two smaller upper bounds of List injective chromatic number

Cited in

(2)

• Exact square coloring of subcubic planar graphs
• Injective (+2)-coloring of planar graphs with girth 5

This page was built for publication: 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4

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