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}^{\prime }(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}^{\prime }(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}^{\prime }(G)$ for any graph $G$, $k\ge 1$, $l\ge 1$, and we present a number of results on ${\chi }_{{\mathcal{O}}_k,l}^{\prime }(G)$.

Détail

DOI : 10.1007/s10587-016-0241-6

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