Contributors: Laboratoire Bordelais de Recherche en Informatique (LaBRI); Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS); Laboratoire d'Informatique Fondamentale d'Orléans (LIFO); Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL); Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA); Indian Institute of Technology Madras (IIT Madras); Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)); Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité); Algorithmes, Graphes et Combinatoire (ALGCO); Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM); Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS); Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO); Laboratoire d'Informatique et des Systèmes (LIS) (Marseille, Toulon) (LIS); Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS); ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017); ANR-17-CE40-0022,HOSIGRA,Homomorphismes de graphes signés(2017)
نبذة مختصرة : International audience ; 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^{\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.
Processing Request
No Comments.