Geodesic
Edge-colouring of graphs and hereditary graph properties
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 1, pp. 87-99 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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)$.
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)$.
DOI : 10.1007/s10587-016-0241-6
Classification : 05C15, 05C35
Keywords: edge-colouring; proper colouring; hereditary graph property 
@article{10_1007_s10587_016_0241_6,
     author = {Dorfling, Samantha and Vetr{\'\i}k, Tom\'a\v{s}},
     title = {Edge-colouring of graphs and hereditary graph properties},
     journal = {Czechoslovak Mathematical Journal},
     pages = {87--99},
     year = {2016},
     volume = {66},
     number = {1},
     doi = {10.1007/s10587-016-0241-6},
     mrnumber = {3483224},
     zbl = {06587875},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0241-6/}
}
TY  - JOUR
AU  - Dorfling, Samantha
AU  - Vetrík, Tomáš
TI  - Edge-colouring of graphs and hereditary graph properties
JO  - Czechoslovak Mathematical Journal
PY  - 2016
SP  - 87
EP  - 99
VL  - 66
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0241-6/
DO  - 10.1007/s10587-016-0241-6
LA  - en
ID  - 10_1007_s10587_016_0241_6
ER  - 
%0 Journal Article
%A Dorfling, Samantha
%A Vetrík, Tomáš
%T Edge-colouring of graphs and hereditary graph properties
%J Czechoslovak Mathematical Journal
%D 2016
%P 87-99
%V 66
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0241-6/
%R 10.1007/s10587-016-0241-6
%G en
%F 10_1007_s10587_016_0241_6
Dorfling, Samantha; Vetrík, Tomáš. Edge-colouring of graphs and hereditary graph properties. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 1, pp. 87-99. doi: 10.1007/s10587-016-0241-6

[1] Basavaraju, M., Chandran, L. S.: A note on acyclic edge coloring of complete bipartite graphs. Discrete Math. 309 (2009), 4646-4648. | DOI | MR | Zbl

[2] Borowiecki, M., Broere, I., Frick, M., Mihók, P., Semanišin, G.: A survey of hereditary properties of graphs. Discuss. Math., Graph Theory 17 (1997), 5-50. | DOI | MR

[3] Czap, J., Mihók, P.: Fractional {$\scr Q$}-edge-coloring of graphs. Discuss. Math., Graph Theory 33 (2013), 509-519. | DOI | MR

[4] Dorfling, M. J., Dorfling, S.: Generalized edge-chromatic numbers and additive hereditary properties of graphs. Discuss. Math., Graph Theory 22 (2002), 349-359. | DOI | MR | Zbl

[5] Erd{ő}s, P., Wilson, R. J.: On the chromatic index of almost all graphs. J. Comb. Theory, Ser. B 23 (1977), 255-257. | DOI | MR

[6] Fiedorowicz, A., Ha{ł}uszczak, M., Narayanan, N.: About acyclic edge colourings of planar graphs. Inf. Process. Lett. 108 (2008), 412-417. | DOI | MR | Zbl

[7] Fouquet, J.-L., Jolivet, J.-L.: Strong edge-colorings of graphs and applications to multi-{$k$}-gons. Ars Comb. 16-A (1983), 141-150. | MR

[8] Ha{ł}uszczak, M., Vateha, P.: On the completeness of decomposable properties of graphs. Discuss. Math., Graph Theory 19 (1999), 229-236. | DOI | MR

[9] Hou, J., Wang, W., Zhang, X.: Acyclic edge coloring of planar graphs with girth at least 5. Discrete Appl. Math. 161 (2013), 2958-2967. | MR | Zbl

[10] K{ö}nig, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 German (1916), 453-465. | DOI | MR

[11] Muthu, R., Narayanan, N., Subramanian, C. R.: On {$k$}-intersection edge colourings. Discuss. Math., Graph Theory 29 (2009), 411-418. | DOI | MR | Zbl

[12] Vizing, V. G.: On an estimate of the chromatic class of a {$p$}-graph. Diskret. Analiz No. 3 (1964), 25-30. | MR

[13] Yang, F., Chen, X.-E., Ma, C.: On the vertex-distinguishing proper edge coloring of composition of complete graph and star. Inf. Process. Lett. 114 (2014), 217-221. | DOI | MR | Zbl

Cité par Sources :