Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
edge-colouring; proper colouring; hereditary graph property
edge-colouring; proper colouring; hereditary graph property
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)$.
References:
[1] Basavaraju, M., Chandran, L. S.: A note on acyclic edge coloring of complete bipartite graphs. Discrete Math. 309 (2009), 4646-4648. DOI 10.1016/j.disc.2009.01.014 | MR 2519206 | Zbl 1192.05044
[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 10.7151/dmgt.1037 | MR 1633268
[3] Czap, J., Mihók, P.: Fractional {$\scr Q$}-edge-coloring of graphs. Discuss. Math., Graph Theory 33 (2013), 509-519. DOI 10.7151/dmgt.1685 | MR 3078888
[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 10.7151/dmgt.1180 | MR 1961213 | Zbl 1030.05039
[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 10.1016/0095-8956(77)90039-9 | MR 0463022
[6] Fiedorowicz, A., Ha{ł}uszczak, M., Narayanan, N.: About acyclic edge colourings of planar graphs. Inf. Process. Lett. 108 (2008), 412-417. DOI 10.1016/j.ipl.2008.07.016 | MR 2458434 | Zbl 1189.05060
[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
[8] Ha{ł}uszczak, M., Vateha, P.: On the completeness of decomposable properties of graphs. Discuss. Math., Graph Theory 19 (1999), 229-236. DOI 10.7151/dmgt.1097 | MR 1768303
[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 3126663 | Zbl 1287.05045
[10] K{ö}nig, D.: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann. 77 German (1916), 453-465. DOI 10.1007/BF01456961 | MR 1511872
[11] Muthu, R., Narayanan, N., Subramanian, C. R.: On {$k$}-intersection edge colourings. Discuss. Math., Graph Theory 29 (2009), 411-418. DOI 10.7151/dmgt.1456 | MR 2574479 | Zbl 1194.05042
[12] Vizing, V. G.: On an estimate of the chromatic class of a {$p$}-graph. Diskret. Analiz No. 3 (1964), 25-30. MR 0180505
[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 10.1016/j.ipl.2013.11.001 | MR 3146289 | Zbl 1296.05081
Search
Partner of
