Edge-colouring of graphs and hereditary graph properties

Dorfling, Samantha, and Vetrík, Tomáš. "Edge-colouring of graphs and hereditary graph properties." Czechoslovak Mathematical Journal 66.1 (2016): 87-99. <http://eudml.org/doc/276772>.

@article{Dorfling2016,
abstract = {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 ^\{\prime \}_\{\{\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 ^\{\prime \}_\{\{\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 ^\{\prime \}_\{\{\mathcal \{S\}\}_k,l\}(G)$ for any graph $G$, $k \ge 1$, $l \ge 1$, and we present a number of results on $\chi ^\{\prime \}_\{\{\mathcal \{O\}\}_k,l\}(G)$.},
author = {Dorfling, Samantha, Vetrík, Tomáš},
journal = {Czechoslovak Mathematical Journal},
keywords = {edge-colouring; proper colouring; hereditary graph property},
language = {eng},
number = {1},
pages = {87-99},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Edge-colouring of graphs and hereditary graph properties},
url = {http://eudml.org/doc/276772},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Dorfling, Samantha
AU - Vetrík, Tomáš
TI - Edge-colouring of graphs and hereditary graph properties
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 1
SP - 87
EP - 99
AB - 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 ^{\prime }_{{\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 ^{\prime }_{{\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 ^{\prime }_{{\mathcal {S}}_k,l}(G)$ for any graph $G$, $k \ge 1$, $l \ge 1$, and we present a number of results on $\chi ^{\prime }_{{\mathcal {O}}_k,l}(G)$.
LA - eng
KW - edge-colouring; proper colouring; hereditary graph property
UR - http://eudml.org/doc/276772
ER -