Exact square coloring of subcubic planar graphs

DOI10.1016/J.DAM.2021.01.007MaRDI QIDQ2659166zbMATH OpenOpenAlexFDO

Authors Florent Foucaud, Hervé Hocquard, Suchismita Mishra, Reza Naserasr, Petru Valicov, N. Narayanan, Éric Sopena

Publication date 25 March 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

injective coloringfullerene graphssubcubic planar graphsexact square coloring

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Molecular structure (graph-theoretic methods, methods of differential topology, etc.) (92E10) Chemical graph theory (05C92)

Abstract: We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G is a vertex-coloring in which any two vertices at distance exactly 2 receive distinct colors. The smallest number of colors used in such a coloring of G is its exact square chromatic number, denoted $ch{i}^{sharp2}(G)$. This notion is related to other types of distance-based colorings, as well as to injective coloring. Indeed, for triangle-free graphs, exact square coloring and injective coloring coincide. We prove tight bounds on special subclasses of planar graphs: subcubic bipartite planar graphs and subcubic K 4-minor-free graphs have exact square chromatic number at most 4. We then turn our attention to the class of fullerene graphs, which are cubic planar graphs with face sizes 5 and 6. We characterize fullerene graphs with exact square chromatic number 3. Furthermore, supporting a conjecture of Chen, Hahn, Raspaud and Wang (that all subcubic planar graphs are injectively 5-colorable) we prove that any induced subgraph of a fullerene graph has exact square chromatic number at most 5. This is done by first proving that a minimum counterexample has to be on at most 80 vertices and then computationally verifying the claim for all such graphs.

Recommendations

• List-Coloring Squares of Sparse Subcubic Graphs
• 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
• The square of a planar cubic graph is 7-colorable
• 2-distance 4-coloring of planar subcubic graphs
• List-coloring the square of a subcubic graph

Cites work

• scientific article; zbMATH DE number 3834025 (Why is no real title available?)
• scientific article; zbMATH DE number 1286500 (Why is no real title available?)
• scientific article; zbMATH DE number 6749528 (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?)
• A partial k-arboretum of graphs with bounded treewidth
• Approximations for  -Colorings of Graphs
• Choosability of the square of planar subcubic graphs with large girth
• Chromatic numbers of exact distance graphs
• Coloring distance graphs: a few answers and many questions
• Colorings and girth of oriented planar graphs
• Colouring exact distance graphs of chordal graphs
• Counterexamples to a conjecture on injective colorings
• Cyclic edge-cuts in fullerene graphs
• Cyclical edge-connectivity of fullerene graphs and \((k,6)\)-cages
• Distance-two colourings of Barnette graphs
• Exact distance colouring in trees
• Exact distance graphs of product graphs
• Injective choosability of subcubic planar graphs with girth 6
• Injective chromatic number of outerplanar graphs
• Injective colorings of planar graphs with few colors
• Labelling Graphs with a Condition at Distance 2
• List 2-facial 5-colorability of plane graphs with girth at least 12
• List Colouring Squares of Planar Graphs
• Mathematical aspects of fullerenes
• Numerical Patterns and Geometrical Configurations
• On the injective chromatic number of graphs
• Parallel recognition of series-parallel graphs
• Recursive generation of IPR fullerenes
• Self 2-distance graphs
• Some results on the injective chromatic number of graphs
• Sparsity. Graphs, structures, and algorithms
• The Chromatic Number of Graph Powers
• The chromatic number of the plane is at least 5
• The square of a planar cubic graph is 7-colorable

Cited in

(7)

• The clique number of the exact distance \(t\)-power graph: complexity and eigenvalue bounds
• 2-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4
• Exact square coloring of certain classes of graphs: complexity and algorithms
• Injective coloring of graphs revisited
• An optimal square coloring of planar graphs
• Improved square coloring of planar graphs
• Exact square coloring of graphs resulting from some graph operations and products

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Exact square coloring of subcubic planar graphs

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