Exact square coloring of subcubic planar graphs
Lists
Only you see this
Abstract
We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G<math><mi is="true">G</mi></math> 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<math><mi is="true">G</mi></math> is its exact square chromatic number, denoted χ[♯2](G)<math><mrow is="true"><msup is="true"><mrow is="true"><mi is="true">χ</mi></mrow><mrow is="true"><mrow is="true"><mo is="true">[</mo><mi is="true">♯</mi><mn is="true">2</mn><mo is="true">]</mo></mrow></mrow></msup><mrow is="true"><mo is="true">(</mo><mi is="true">G</mi><mo is="true">)</mo></mrow></mrow></math>. 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 K4<math><msub is="true"><mrow is="true"><mi is="true">K</mi></mrow><mrow is="true"><mn is="true">4</mn></mrow></msub></math>-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.
BibTeX
@article{foucaud2020exact,
author = {Florent Foucaud and Hervé Hocquard and Suchismita Mishra and Narayanan Narayanan and Reza Naserasr and Éric Sopena and Petru Valicov},
title = {{Exact square coloring of subcubic planar graphs}},
journal = {Discret. Appl. Math.},
year = {2020},
doi = {10.1016/j.dam.2021.01.007},
}Loading related content...