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 P and l ⩾ 1 we define \(X{'_{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 P. We present a necessary and sufficient condition for the existence of \(X{'_{P,l}}\)(G). We focus on edge-colourings of graphs with respect to the hereditary properties O k and S k , where O k contains all graphs whose components have order at most k+1, and S k contains all graphs of maximum degree at most k. We determine the value of \(X{'_{{S_k},l}}(G)\) for any graph G, k ⩾ 1, l ⩾ 1, and we present a number of results on \(X{'_{{O_k},l}}(G)\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Basavaraju, L. S. Chandran: A note on acyclic edge coloring of complete bipartite graphs. Discrete Math. 309 (2009), 4646–4648.
M. Borowiecki, I. Broere, M. Frick, P. Mihok, G. Semanišin: A survey of hereditary properties of graphs. Discuss. Math., Graph Theory 17 (1997), 5–50.
J. Czap, P. Mihok: Fractional Q-edge-coloring of graphs. Discuss. Math., Graph Theory 33 (2013), 509–519.
M. J. Dorfling, S. Dorfling: Generalized edge-chromatic numbers and additive hereditary properties of graphs. Discuss. Math., Graph Theory 22 (2002), 349–359.
P. Erdős, R. J. Wilson: On the chromatic index of almost all graphs. J. Comb. Theory, Ser. B 23 (1977), 255–257.
A. Fiedorowicz, M. Ha luszczak, N. Narayanan: About acyclic edge colourings of planar graphs. Inf. Process. Lett. 108 (2008), 412–417.
J.-L. Fouquet, J.-L. Jolivet: Strong edge-colorings of graphs and applications to multi-k-gons. Ars Comb. 16-A (1983), 141–150.
M. Ha luszczak, P. Vateha: On the completeness of decomposable properties of graphs. Discuss. Math., Graph Theory 19 (1999), 229–236.
J. Hou, W. Wang, X. Zhang: Acyclic edge coloring of planar graphs with girth at least 5. Discrete Appl. Math. 161 (2013), 2958–2967.
D. Konig: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 (1916), 453–465. (In German.)
R. Muthu, N. Narayanan, C. R. Subramanian: On k-intersection edge colourings. Discuss. Math., Graph Theory 29 (2009), 411–418.
V. G. Vizing: On an estimate of the chromatic class of a p-graph. Diskret. Analiz No. 3 (1964), 25–30
F. Yang, X.-E. Chen, C. Ma: On the vertex-distinguishing proper edge coloring of composition of complete graph and star. Inf. Process. Lett. 114 (2014), 217–221.
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of the second author has been supported by the National Research Foundation of South Africa; Grant numbers: 91499, 90793.
Rights and permissions
About this article
Cite this article
Dorfling, S., Vetrík, T. Edge-colouring of graphs and hereditary graph properties. Czech Math J 66, 87–99 (2016). https://doi.org/10.1007/s10587-016-0241-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10587-016-0241-6