Distance-two colourings of Barnette graphs

DOI10.1016/j.ejc.2020.103210zbMath1458.05065arXiv1807.01410MaRDI QIDQ2225415

Carlos Subi, Tomás Feder, Pavol Hell

Publication date: 8 February 2021

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Barnette conjecture; cubic planar graph

Mathematics Subject Classification ID

05C15: Coloring of graphs and hypergraphs

05C12: Distance in graphs

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on 3-connected cubic planar graphs
• Choosability of the square of planar subcubic graphs with large girth
• The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
• Hamiltonian circuits in polytopes with even sided faces
• Colorings of plane graphs: a survey
• On generating planar graphs
• 2-distance 4-colorability of planar subcubic graphs with girth at least 22
• List-Coloring Squares of Sparse Subcubic Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• A class of Hamiltonian polytopes
• Nonhamiltonian 3-Connected Cubic Planar Graphs
• A Computer-Assisted Proof of the Barnette--Goodey Conjecture: Not Only Fullerene Graphs Are Hamiltonian
• On Hamiltonian Circuits
• Long cycles in fullerene graphs