DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 22(2) (2002) 349-359
DOI: 10.7151/dmgt.1180

GENERALIZED EDGE-CHROMATIC NUMBERS AND ADDITIVE HEREDITARY PROPERTIES OF GRAPHS

 Michael J. Dorfling

Department of Mathematics
Faculty of Science
Rand Afrikaans University
P.O. Box 524, Auckland Park, 2006 South Africa

Samantha Dorfling

Department of Mathematics and Applied Mathematics
Faculty of Science
University of the Free State
P.O. Box 339, Bloemfontein, 9300 South Africa
e-mail: DorfliS@sci.uovs.ac.za

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, ℑkOkW*kSk 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