Infinite families of planar graphs of a given injective chromatic number

作     者：Daneels, Matias Goedgebeur, Jan Renders, Jarne 

作者机构：Department of Computer Science KU Leuven Campus Kulak-Kortrijk Kortrijk8500 Belgium Department of Applied Mathematics Computer Science and Statistics Ghent University Ghent9000 Belgium 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Graphic methods 

摘      要：An injective colouring of a graph is a colouring in which every two vertices sharing a common neighbour receive a different colour. Chen, Hahn, Raspaud and Wang conjectured that every planar graph of maximum degree ∆ ≥ 3 admits an injective colouring with at most ⌊3∆/2⌋ colours. This was later disproved by Lužar and Škrekovski for certain small and even values of ∆ and they proposed a new refined conjecture. Using an algorithm for determining the injective chromatic number of a graph, i.e. the smallest number of colours for which the graph admits an injective colouring, we give computational evidence for Lužar and Škrekovski’s conjecture and extend their results by presenting an infinite family of 3-connected planar graphs for each ∆ (except for 4) attaining their bound, whereas they only gave a finite amount of examples for each ∆. Hence, together with another infinite family of maximum degree 4, we provide infinitely many counterexamples to the conjecture by Chen et al. for each ∆ if 4 ≤ ∆ ≤ 7 and every even ∆ ≥ 8. We provide similar evidence for analogous conjectures by La and Štorgel and Lužar, Škrekovski and Tancer when the girth is restricted as well. Also in these cases we provide infinite families of 3-connected planar graphs attaining the bounds of these conjectures for certain maximum degrees ∆ ≥ *** Codes 05C10, 05C15, 05C85, 68R10, 90C35 Copyright © 2024, The Authors. All rights reserved.