Infinite families of planar graphs of a given injective chromatic number

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 finitely many 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 Δ ≥ 3.