Discussiones
Mathematicae Graph Theory 22(2) (2002) 349-359
DOI: https://doi.org/10.7151/dmgt.1180
GENERALIZED EDGE-CHROMATIC NUMBERS AND ADDITIVE HEREDITARY PROPERTIES OF GRAPHS
Michael J. Dorfling
Department of Mathematics |
Samantha Dorfling
Department of Mathematics and Applied Mathematics |
Abstract
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. Let P and Q be hereditary properties of graphs. The generalized edge-chromatic number ρ′Q(P) is defined as the least integer n such that P ⊆ nQ. We investigate the generalized edge-chromatic numbers of the properties →H, ℑk, Ok, W*k, Sk and Dk.Keywords: property of graphs, additive, hereditary, generalized edge-chromatic number.
2000 Mathematics Subject Classification: 05C15.
References
[1] | M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. |
[2] | M. Borowiecki and M. Hałuszczak, Decompositions of some classes of graphs, Report No. IM-3-99 (Institute of Mathematics, Technical University of Zielona Góra, 1999). |
[3] | I. Broere and M. J. Dorfling, The decomposability of additive hereditary properties of graphs, Discuss. Math. Graph Theory 20 (2000) 281-291, doi: 10.7151/dmgt.1127. |
[4] | I. Broere, M.J. Dorfling, J.E Dunbar and M. Frick, A path(ological) partition problem, Discuss. Math. Graph Theory 18 (1998) 113-125, doi: 10.7151/dmgt.1068. |
[5] | I. Broere, S. Dorfling and E. Jonck, Generalized chromatic numbers and additive hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 259-270, doi: 10.7151/dmgt.1174. |
[6] | J. Nesetril and V. Rödl, Simple proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica 1 (2) (1981) 199-202, doi: 10.1007/BF02579274. |
Received 13 June 2001
Revised 5 April 2002
Close