Edge-colouring of graphs and hereditary graph properties

Dorfling, Samantha ; Vetrík, Tomáš

Czechoslovak Mathematical Journal, Tome 66 (2016) no. 1, pp. 87-99.

Résumé

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph $G$, a hereditary graph property ${\mathcal P}$ and $l \ge 1$ we define $\chi '_{{\mathcal P},l}(G)$ to be the minimum number of colours needed to properly colour the edges of $G$, such that any subgraph of $G$ induced by edges coloured by (at most) $l$ colours is in ${\mathcal P}$. We present a necessary and sufficient condition for the existence of $\chi '_{{\mathcal P},l}(G)$. We focus on edge-colourings of graphs with respect to the hereditary properties ${\mathcal O}_k$ and ${\mathcal S}_k$, where ${\mathcal O}_k$ contains all graphs whose components have order at most $k+1$, and ${\mathcal S}_k$ contains all graphs of maximum degree at most $k$. We determine the value of $\chi '_{{\mathcal S}_k,l}(G)$ for any graph $G$, $k \ge 1$, $l \ge 1$, and we present a number of results on $\chi '_{{\mathcal O}_k,l}(G)$.

Détail

DOI : 10.1007/s10587-016-0241-6

Classification : 05C15, 05C35
Mots-clés : edge-colouring; proper colouring; hereditary graph property