Geodesic
A survey of hereditary properties of graphs
Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 5-50.

Voir la notice de l'article provenant de la source Library of Science

In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
Keywords: hereditary property of graphs, vertex partition, reducible property, graph invariants, complexity 
@article{DMGT_1997_17_1_a0,
     author = {Borowiecki, Mieczys{\l}aw and Broere, Izak and Frick, Marietjie and Mih\'ok, Peter and Semani\v{s}in, Gabriel},
     title = {A survey of hereditary properties of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {5--50},
     publisher = {mathdoc},
     volume = {17},
     number = {1},
     year = {1997},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a0/}
}
TY  - JOUR
AU  - Borowiecki, Mieczysław
AU  - Broere, Izak
AU  - Frick, Marietjie
AU  - Mihók, Peter
AU  - Semanišin, Gabriel
TI  - A survey of hereditary properties of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1997
SP  - 5
EP  - 50
VL  - 17
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a0/
LA  - en
ID  - DMGT_1997_17_1_a0
ER  - 
%0 Journal Article
%A Borowiecki, Mieczysław
%A Broere, Izak
%A Frick, Marietjie
%A Mihók, Peter
%A Semanišin, Gabriel
%T A survey of hereditary properties of graphs
%J Discussiones Mathematicae. Graph Theory
%D 1997
%P 5-50
%V 17
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a0/
%G en
%F DMGT_1997_17_1_a0
Borowiecki, Mieczysław; Broere, Izak; Frick, Marietjie; Mihók, Peter; Semanišin, Gabriel. A survey of hereditary properties of graphs. Discussiones Mathematicae. Graph Theory, Tome 17 (1997) no. 1, pp. 5-50. http://geodesic.mathdoc.fr/item/DMGT_1997_17_1_a0/

[1] K. Appel and W. Haken, Every planar graph is four colourable, Illinois Jour. Math. 21(1977) 429-567.

[2] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely $(m,k)^τ$-colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22.

[3] G. Birkhoff, Lattice theory (AMS, New York, 1948).

[4] B. Bollobás and B. Manvel, Optimal vertex partitions, Bull. London Math. Soc. 11(1979) 113-116, doi: 10.1112/blms/11.2.113.

[5] B. Bollobás and N. Sauer, Uniquely colourable graphs with large girth, Canad. J. Math. 28 (1976) no. 2 1340-1344; MR55#2632.

[6] B. Bollobás and A.G. Thomason, Uniquely partitionable graphs, J. London Math. Soc. (2) 16 (1977) 403-410.

[7] 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.

[8] J. A. Bondy and U. S. Murty, Graph theory with applications (American Elsevier Publishing Co., Inc., New York, 1976); MR54#117.

[9] O. V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskret. Analiz. 28(1976) 3-11.

[10] O. V. Borodin, On acyclic colouring of planar graphs, Discrete Math.25(1979) 211-236, doi: 10.1016/0012-365X(79)90077-3.

[11] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs (manuscript) 1997.

[12] M. Borowiecki, I. Broere and P. Mihók, On generalized list colourings of graphs (manuscript) 1997.

[13] M. Borowiecki, E. Drgas-Burchardt and P. Mihók, Generalized list colouring of graphs, Discuss. Mathematicae Graph Theory 15(1995) 185-193, doi: 10.7151/dmgt.1016.

[14] M. Borowiecki, M. Hałuszczak and M. Skowronska, Minimal reducible bounds for 1-non-outerplanar graphs, Report IM-1-96, Inst. Math., Technical Univ. of Zielona Góra, Zielona Góra, 1996.

[15] M. Borowiecki, J. Ivanco, P. Mihók and G. Semanišin, Sequences realizable by maximal k-degenerate graphs, J. Graph Theory 19(1995) 117-124; MR96e:05078.

[16] M. Borowiecki and D. Michalak, Generalized independence and domination in graphs, Report IM-96, Inst. Math., Technical Univ. of Zielona Góra, Zielona Góra, 1996.

[17] 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.

[18] P. Borowiecki and J. Ivanco, P-bipartitions of minor hereditary properties Discussiones Mathematicae Graph Theory 17 (1997) 89-93.

[19] I. Broere and M. Frick, On the order of uniquely (k,m)-colourable graphs, Discrete mathematics 82 (1990) 225-232, doi: 10.1016/0012-365X(90)90200-2.

[20] I. Broere, M. Frick and P. Mihók, On the order of uniquely partitionable graphs Discussiones Mathematicae Graph Theory 17 (1997) 115-125.

[21] I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties Discussiones Mathematicae Graph Theory 17 (1997) 51-66. (manuscript).

[22] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37(1941) 194-197, doi: 10.1017/S030500410002168X.

[23] J.I. Brown, The complexity of generalized graph coloring, Discrete Appl. Math. 69(1996) 257-270, doi: 10.1016/0166-218X(96)00096-0.

[24] J. Bucko, P. Mihók and M. Voigt, Uniquely partitionable planar graphs (submitted) 1996.

[25] S.A. Burr and M.S. Jacobson, On inequalities involving vertex partition parameter of graphs, Congr. Numerantium 70(1990) 159-170.

[26] G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, Journal of Combinatorial Theory (B) 10(1971) 12-41; MR44#2645.

[27] G. Chartrand and J. P. Geller, Uniquely colourable planar graphs, J. Comb. Theory 6(1969) 271-278; MR39#2661.

[28] G. Chartrand, H.V. Kronk and C.E. Wall, The point-arboricity of a graph, Israel J. Math. 6(1968) 169-175, doi: 10.1007/BF02760181.

[29] G. Chartrand and L. Lesniak, Graphs and digraphs (Wadsworth Brooks/Cole, Monterey California, 1986).

[30] E. J. Cockayne, S. T. Hedetniemi and R. Laskar, Gallai theorems for graphs, hypergraphs and set systems, Discrete Math. 72(1988) 35-47, doi: 10.1016/0012-365X(88)90192-6.

[31] L. J. Cowen, R. H. Cowen and D. R. Woodall, Defective colorings of graphs in surfaces; partitions into subgraphs of bounded valency, Journal of Graph Theory 10(1986) 187-195, doi: 10.1002/jgt.3190100207.

[32] L. J. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited (to appear).

[33] K. Edwards, The complexity of some graph colouring problems, Discrete Appl. Math. 36(1992) 131-140, doi: 10.1016/0166-218X(92)90227-2.

[34] P. Erdős, Some recent results on extremal problems in graph theory, in: P. Rosentstiehl, ed., Theory of graphs vol. 38 (Gordon and Breach New York, Dunod Paris, 1967) 117-123; MR37#2634.

[35] P. Erdős, On some new inequalities concerning extremal properties of graphs, in: P. Erdős and G.Katona, eds., Theory of graphs vol. 38 (Academic Press, New York, 1968) 77-81; MR38#1026.

[36] P. Erdős, A. L. Rubin and H. Taylor, Choosability in graphs Proc. West Coast Conf. on Combin., Graph Theory and Computing (Congressus Numerantium XXVI, 1979) 125-157.

[37] Z. Filáková, P. Mihók and G. Semanišin, On maximal k-degenerate graphs (to appear in Mathematica Slovaca in 1997).

[38] M. Frick, A survey of (m,k)-colourings, in: J. Gimbel c.a, ed., Quo Vadis, Graph Theory? Annals of Discrete Mathematics vol. 55 (North-Holland, Amsterdam, 1993) 45-58.

[39] M. Frick and M. A. Henning, Extremal results on defective colorings of graphs, Discrete mathematics 126(1994) 151-158, doi: 10.1016/0012-365X(94)90260-7.

[40] T. Gallai, Uber extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2(1959) 133 - 138 (German); MR24#A1222.

[41] T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hung. Acad. Sci.8 (1963) 165 - 192 (German); MR32#5540.

[42] M. Garey, D. Johnson and R.E. Tarjan, The planar hamiltonian circuit problem is NP-complete, SIAM J. Computing 5(1976) 704-714, doi: 10.1137/0205049.

[43] M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness (W.H. Freeman, San Francisco, CA, 1979).

[44] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Comput. Sci. 1(1976) 237-267, doi: 10.1016/0304-3975(76)90059-1.

[45] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94, doi: 10.1016/0012-365X(91)90166-Y.

[46] R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey theory (A Wiley-Interscience Publication, New York, 1980).

[47] G. Gratzer, Universal algebra (D. van Nostrand and Co., 1968).

[48] D. L. Greenwell, R. L. Hemminger and J. Klerlein, Forbidden subgraphs Pro. 4th S-E Conf. Combinatorics, Graph Theory and Computing (Utilitas Math., Winnipeg, Man., 1973) 389-394; MR50#6924.

[49] B. Grunbaum, Acyclic colorings of planar graphs, Israel J. Math. 14(1973) 390-408, doi: 10.1007/BF02764716.

[50] S. Gutner, The complexity of planar graph choosability, Discrete Math.159(1996) 119-130, doi: 10.1016/0012-365X(95)00104-5.

[51] S.L. Hakimi, E. Schmeichel and J. Weinstein, Partitioning planar graphs into independent sets and forest, Congressus Numerantium 78(1990) 109-118.

[52] F. Harary, S. T. Hedetniemi and R. W. Robinson, Uniquely colourable graphs, J. Comb. Theory 6(1969) 264-270; MR39#99.

[53] S. T. Hedetniemi, Hereditary properties of graphs, J. Combin. Theory (B) 14(1973) 94-99; MR47#4861.

[54] S. T. Hedetniemi and R. Laskar, Connected domination in graphs, in: B. Bollobás, ed., Graph theory and combinatorics (Academic Press, London, 1984) 209-218.

[55] P. Hell and J. Nesetril, On the complexity of H-coloring, J. Comb. Theory (B) 48(1990) 92-110, doi: 10.1016/0095-8956(90)90132-J.

[56] M. A. Henning and H. C. Swart, Bounds on a generalized domination parameter, Quaestiones Math. 13(1990) 237-253, doi: 10.1080/16073606.1990.9631615.

[57] T. R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995).

[58] L. Kászonyi and Zs. Tuza, Saturated graphs with minimal number of edges, Journal of Graph Theory 10 (1986) 203-210, doi: 10.1002/jgt.3190100209.

[59] S. Klavžar and M. Petkovsek, On characterizations with forbidden subgraphs, Colloquia Mathematica Societatis János Bolyai, 52. Combinatorics, Eger 2(1987) 331-339.

[60] A. V. Kostochka, M. Stiebitz and B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math. 162(1996) 299-303, doi: 10.1016/0012-365X(95)00294-7.

[61] J. Kratochvil and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors (submitted).

[62] J. Kratochvil, P. Mihók and G. Semanišin, Graphs maximal with respect to hom-properties (submitted).

[63] J. Kratochvil and Zs. Tuza, Algorithmic complexity of list colorings, Discrete Appl. Math. 50 (1994) 297-302, doi: 10.1016/0166-218X(94)90150-3.

[64] R. Lick and A. T. White, k-degenerate graphs, Canadian Journal of Mathematics 22(1970) 1082-1096; MR42#1715.

[65] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#2442.

[66] P. Mihók, The minimal reducible bounds for degenerate classes of graphs (manuscript).

[67] P. Mihók, On graphs critical with respect to vertex partition numbers, Discrete Math. 37(1981) 123-126, doi: 10.1016/0012-365X(81)90146-1.

[68] P.Mihók, On vertex partition numbers of graphs, in: M. Fiedler, ed., Graphs and Other Combinatorial Topics, Proc. of the Third Czechoslovak Symp. on Graph Theory (Praha 1982) (Teubner-Texte, Leipzig, 1983) 15-18.

[69] 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.

[70] P. Mihók, On graphs critical with respect to generalized independence numbers, Colloquia Mathematica Societatis János Bolyai 52. Combinatorics, Eger 2(1987) 417-421.

[71] P. Mihók, On the minimal reducible bound for outerplanar and planar graphs, Discrete Math. 150(1996) 431-435, doi: 10.1016/0012-365X(95)00211-E.

[72] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted).

[73] P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Mathematicae - Graph Theory 15(1995) 11-18; MR96c:05149.

[74] P. Mihók and R. Vasky, On the factorization of reducible properties of graphs into irreducible factors, Discussiones Mathematicae - Graph Theory 15(1995) 195-203; MR96i:05134.

[75] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11(1977) 101-106.

[76] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3(1955) 161-162.

[77] J. Nesetril, Graph homomorphism and their structure, in: Y. Alavi and A. Schwenk, eds., Graph Theory, Combinatorics and Applications: Proceedings of the Seventh Quadrennial International Conference on the Theory and Applications of Graphs vol. 2 (, 1995) 825-832.

[78] J. Nesetril and V. Rodl, Partitions of vertices, Comment. Math. Univ. Carolinae 17(1976) no. 1 85-95; MR54#173.

[79] J. Nieminen, Two bounds for the domination number of a graph, J. Inst. Math. Appl. 14(1974) 183-187; MR50#9708.

[80] L. T. Ollmann, $K_{2,2}$-saturated graphs with minimal number of edges Proc. 3rd S-E Conference on Combinatorics, Graph Theory and Computing (Boca Raton, Fla., 1972) (Florida Atlantic Univ., Boca Raton, Fla., 1972) 367-392; MR50#1970.

[81] O. Ore, Theory of graphs(Amer. Math. Soc. Colloq. Publ., vol. XXXVIII, AMS Providence, 1962); MR27#740.

[82] K. S. Poh, On the linear vertex-arboricity of a planar graph, Journal of Graph Theory 14(1990) 73-75, doi: 10.1002/jgt.3190140108.

[83] E. R. Scheinerman, On the structure of hereditary classes of graphs, Journal of Graph Theory 10(1986) 545-551, doi: 10.1002/jgt.3190100414.

[84] G. Semanišin, On some variations of extremal graph problems Discussiones Mathematicae Graph Theory 17 (1997) 67-76.

[85] J. M. S. Simoes-Pereira, Joins of n-degenerate graphs and uniquely (m,n)- partitionable graphs, J. Combin. Theory 21(1976) 21-29, doi: 10.1016/0095-8956(76)90023-X.

[86] M. Simonovits, A method for solving extremal problems in graph theory, in: P. Erdős and G. Katona, eds., Theory of graphs (Academic Press, New York, 1968) 279-319; MR38#2056.

[87] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. additional chromatical conditions, Discrete Mathematics 7(1974) 349-376; MR49#2459.

[88] M. Simonovits, Extremal graph theory, in: L. W. Beineke and R. J. Wilson, eds., Selected topics in graph theory vol. 2 (Academic Press, London, 1983) 161-200.

[89] M. Simonovits, Paul Erdős influence on extremal graph theory, in: R.L. Graham and J. Nesetril, eds., The mathematics of Paul Erdős, II, Algorithms and Combinatorics 14 (Springer-Verlag, 1997) 148-192.

[90] S.K. Stein, B-sets and planar graphs, Pacific J. Math. 37(1971) 217-224; MR46#5180.

[91] L. Stockmeyer, Planar 3-colorability is polynomial complete, SIGACT News (ACM Publication) 5(1973) 19-25, doi: 10.1145/1008293.1008294.

[92] C. Thomassen, Color-critical graphs on fixed surface, Report, Technical University of Denmark, Lyngby, 1995.

[93] C. Thomassen, Decomposing a planar into degenerate graphs, J. Combin. Theory (B) 65(1995) 305-314, doi: 10.1006/jctb.1995.1057.

[94] B. Toft, A survey of Hadwiger's conjecture, Preprints, Institut for Matematik og Datalogi, Odense Universitet, January 1996.

[95] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48(1941) 436-452 (Hungarian); MR8,284j.

[96] P. Turán, On the theory of graph, Colloquia Math. 3(1954) 19-30; MR15,476b.

[97] Zs. Tuza, C₄-saturated graphs of minimum size, Acta Univ.Carolin.- Math. Phys. 30(1989) 161-167.

[98] Zs. Tuza, Graph colorings with local constraints - a survey, Discussiones Mathematicae Graph Theory 17 (1997) (to appear).

[99] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3(1964) 25-30 (Russian); MR34#101.

[100] V. G. Vizing, Colouring the vertices of a graph in prescribed colours, Diskret. Analiz 29(1976) 3-10 (Russian).

[101] M.L. Weaver and D.B. West Relaxed chromatic number of graphs, Graphs and Combinatorics 10(1994) 75-93, doi: 10.1007/BF01202473.

[102] E. Welzl, Color families are dense, Theoretical Computer Sci. 17(1982) 29-41, doi: 10.1016/0304-3975(82)90129-3.

[103] D. Woodall, Improper colorings of graphs, in: R. Nelson and R.J. Wilson, eds., Graph Colorings (Longman, New York, 1990) 45-64.

[104] X. Zhu, Uniquely H-colorable graphs with large girth, Journal of Graph Theory 23(1996) 33-41, doi: 10.1002/(SICI)1097-0118(199609)23:133::AID-JGT3>3.0.CO;2-L.

[105] A.A. Zykov, On some problems of linear complexes, Mat. Sbornik N. S.24(1949) 163-188.