Infinite families of planar graphs of a given injective chromatic number
| Autor: | Daneels, Matias, Goedgebeur, Jan, Renders, Jarne |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $\Delta \ge 3$ admits an injective colouring with at most $\lfloor 3\Delta/2\rfloor$ colours. This was later disproved by Lu\v{z}ar and \v{S}krekovski for certain small and even values of $\Delta$ 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\v{z}ar and \v{S}krekovski's conjecture and extend their results by presenting an infinite family of $3$-connected planar graphs for each $\Delta$ (except for $4$) attaining their bound, whereas they only gave a finite amount of examples for each $\Delta$. Hence, together with another infinite family of maximum degree $4$, we provide infinitely many counterexamples to the conjecture by Chen et al. for each $\Delta$ if $4\le \Delta \le 7$ and every even $\Delta \ge 8$. We provide similar evidence for analogous conjectures by La and \v{S}torgel and Lu\v{z}ar, \v{S}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 $\Delta\geq 3$. Comment: 15 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|