2020/09/30 by Florent Foucaud, Hervé Hocquard, Suchismita Mishra +5
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Discrete mathematics #Edge coloring #Geometry #Graph #Graph Labeling and Dimension Problems #Line graph #Mathematics #Planar #Planar graph #Square (algebra) #cs.DM #graph theory and CDMA systems #math.CO
paper · pdf · doi:10.1016/j.dam.2021.01.007
published as Discrete Applied Mathematics 293:74-89, 2021 · 19 pages, 13 figures
arxiv created 2021/01/24 · openalex publication_date 2021/01/30 · arxiv updated 2021/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 χ\sharp 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.