A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1167,
author = {Gabriel Semani\v sin},
title = {On generating sets of induced-hereditary properties},
journal = {Discussiones Mathematicae Graph Theory},
volume = {22},
year = {2002},
pages = {183-192},
zbl = {1018.05089},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1167}
}
Gabriel Semanišin. On generating sets of induced-hereditary properties. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 183-192. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1167/
[000] [1] B. Bollobás and A.G. Thomason, Hereditary and monotone properties of graphs, in: R.L. Graham and J. Nesetril, eds., The mathematics of Paul Erdős, II, Algorithms and Combinatorics 14 (Springer-Verlag, 1997) 70-78. | Zbl 0866.05030
[001] [2] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037. | Zbl 0902.05026
[002] [3] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 42-69.
[003] [4] I. Broere and J.Bucko, Divisibility in additive hereditary graph properties and uniquely partitionable graphs, Tatra Mountains Math. Publications 18 (1999) 79-87. | Zbl 0951.05034
[004] [5] G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory (B) 10 (1971) 12-41, doi: 10.1016/0095-8956(71)90065-7. | Zbl 0223.05101
[005] [6] E.J. Cockayne, Color classes for r-graphs, Canad. Math. Bull. 15 (3) (1972) 349-354, doi: 10.4153/CMB-1972-063-2. | Zbl 0254.05106
[006] [7] E.J. Cockayne, G.G. Miller and G. Prins, An interpolation theorem for partitions which are complete with respect to hereditary properties, J. Combin. Theory (B) 13 (1972) 290-297, doi: 10.1016/0095-8956(72)90065-2. | Zbl 0268.05006
[007] [8] M. Frick, A survey of (m,k)-colorings, in: J. Gimbel c.a, ed., Quo Vadis, Graph Theory? A source book for challenges and directions, Annals of Discrete Mathematics 55 (North-Holland, Amsterdam, 1993) 45-57.
[008] [9] S.T. Hedetniemi, On hereditary properties of graphs, J. Combin. Theory (B) 14 (1973) 94-99, doi: 10.1016/S0095-8956(73)80009-7. | Zbl 0249.05116
[009] [10] T.R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). | Zbl 0971.05046
[010] [11] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: M. Borowiecki and Z. Skupień, eds., Graphs, hypergraphs and matroids (Zielona Góra, 1985) 49-58. | Zbl 0623.05043
[011] [12] P. Mihók, Unique factorization theorem, Discuss. Math. Graph Theory 20 (2000) 143-154, doi: 10.7151/dmgt.1114. | Zbl 0968.05032
[012] [13] P. Mihók, G. Semanišin and R. Vasky, Additive and Hereditary Properties of Graphs are Uniquely Factorizable into Irreducible Factors, J. Graph Theory 33 (2000) 44-53, doi: 10.1002/(SICI)1097-0118(200001)33:1<44::AID-JGT5>3.0.CO;2-O | Zbl 0942.05056
[013] [14] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11 (1977) 101-106. | Zbl 0348.05109