| Title:
|
Edge-colouring of graphs and hereditary graph properties (English) |
| Author:
|
Dorfling, Samantha |
| Author:
|
Vetrík, Tomáš |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
1 |
| Year:
|
2016 |
| Pages:
|
87-99 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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)$. (English) |
| Keyword:
|
edge-colouring |
| Keyword:
|
proper colouring |
| Keyword:
|
hereditary graph property |
| MSC:
|
05C15 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 06587875 |
| idMR:
|
MR3483224 |
| DOI:
|
10.1007/s10587-016-0241-6 |
| . |
| Date available:
|
2016-04-07T14:56:57Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144874 |
| . |
| Reference:
|
[1] Basavaraju, M., Chandran, L. S.: A note on acyclic edge coloring of complete bipartite graphs.Discrete Math. 309 (2009), 4646-4648. Zbl 1192.05044, MR 2519206, 10.1016/j.disc.2009.01.014 |
| Reference:
|
[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. MR 1633268, 10.7151/dmgt.1037 |
| Reference:
|
[3] Czap, J., Mihók, P.: Fractional {$\scr Q$}-edge-coloring of graphs.Discuss. Math., Graph Theory 33 (2013), 509-519. MR 3078888, 10.7151/dmgt.1685 |
| Reference:
|
[4] Dorfling, M. J., Dorfling, S.: Generalized edge-chromatic numbers and additive hereditary properties of graphs.Discuss. Math., Graph Theory 22 (2002), 349-359. Zbl 1030.05039, MR 1961213, 10.7151/dmgt.1180 |
| Reference:
|
[5] Erd{ő}s, P., Wilson, R. J.: On the chromatic index of almost all graphs.J. Comb. Theory, Ser. B 23 (1977), 255-257. MR 0463022, 10.1016/0095-8956(77)90039-9 |
| Reference:
|
[6] Fiedorowicz, A., Ha{ł}uszczak, M., Narayanan, N.: About acyclic edge colourings of planar graphs.Inf. Process. Lett. 108 (2008), 412-417. Zbl 1189.05060, MR 2458434, 10.1016/j.ipl.2008.07.016 |
| Reference:
|
[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 0737086 |
| Reference:
|
[8] Ha{ł}uszczak, M., Vateha, P.: On the completeness of decomposable properties of graphs.Discuss. Math., Graph Theory 19 (1999), 229-236. MR 1768303, 10.7151/dmgt.1097 |
| Reference:
|
[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. Zbl 1287.05045, MR 3126663 |
| Reference:
|
[10] K{ö}nig, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre.Math. Ann. 77 German (1916), 453-465. MR 1511872, 10.1007/BF01456961 |
| Reference:
|
[11] Muthu, R., Narayanan, N., Subramanian, C. R.: On {$k$}-intersection edge colourings.Discuss. Math., Graph Theory 29 (2009), 411-418. Zbl 1194.05042, MR 2574479, 10.7151/dmgt.1456 |
| Reference:
|
[12] Vizing, V. G.: On an estimate of the chromatic class of a {$p$}-graph.Diskret. Analiz No. 3 (1964), 25-30. MR 0180505 |
| Reference:
|
[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. Zbl 1296.05081, MR 3146289, 10.1016/j.ipl.2013.11.001 |
| . |
