Exact square coloring of subcubic planar graphs

DOI10.1016/J.DAM.2021.01.007zbMATH Open1460.05050arXiv2009.00843OpenAlexW3081744052MaRDI QIDQ2659166FDOQ2659166

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

Publication date: 25 March 2021

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

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.

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)

Cites Work

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

Cited In (7)

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

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)