Exact square coloring of subcubic planar graphs

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 ${\chi }^{♯2}(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.

arXiv comment19 pages, 13 figures

References in corpus (8)

• The Generation of Fullerenes
• The chromatic number of the plane is at least 5
• Recursive generation of IPR fullerenes
• Exact distance coloring in trees
• Self 2-distance graphs
• Coloring distance graphs: a few answers and many questions
• Injective choosability of subcubic planar graphs with girth 6
• On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs

Cited by in corpus (4)

• Injective coloring of graphs revisited
• Characterizing and recognizing exact-distance squares of graphs
• On the Djoković-Winkler relation and its closure in subdivisions of fullerenes, triangulations, and chordal graphs
• $2$-distance, injective, and exact square list-coloring of planar graphs with maximum degree 4