A survey of hereditary properties of graphs

Mieczysław Borowiecki ; Izak Broere ; Marietjie Frick ; Peter Mihók ; Gabriel Semanišin

Discussiones Mathematicae Graph Theory, Tome 17 (1997), p. 5-50 / Harvested from The Polish Digital Mathematics Library

Résumé

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.

Détail

Publié le : 1997-01-01

Zbl 0902.05026

EUDML-ID : urn:eudml:doc:270405

Bibliographie

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

[001] [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. | Zbl 0870.05026

[002] [3] G. Birkhoff, Lattice theory (AMS, New York, 1948). | Zbl 0033.10103

[003] [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. | Zbl 0423.05021

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

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

[006] [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. | Zbl 0866.05030

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

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

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

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

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

[012] [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. | Zbl 0845.05046

[013] [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. | Zbl 0961.05038

[014] [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. | Zbl 0813.05061

[015] [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. | Zbl 0958.05102

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

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

[018] [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. | Zbl 0712.05024

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

[020] [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). | Zbl 0902.05027

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

[022] [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. | Zbl 0879.05029

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

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

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

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

[027] [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. | Zbl 0164.54201

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

[029] [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. | Zbl 0728.05050

[030] [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. | Zbl 0596.05024

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

[032] [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. | Zbl 0758.05050

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

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

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

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

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

[038] [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. | Zbl 0794.05029

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

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

[041] [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. | Zbl 0346.05110

[042] [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). | Zbl 0411.68039

[043] [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. | Zbl 0338.05120

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

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

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

[047] [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. | Zbl 0312.05128

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

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

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

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

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

[053] [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. | Zbl 0548.05055

[054] [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. | Zbl 0639.05023

[055] [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. | Zbl 0709.05029

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

[057] [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. | Zbl 0593.05041

[058] [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. | Zbl 0698.05048

[059] [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. | Zbl 0871.05024

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

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

[062] [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. | Zbl 0807.68055

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

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

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

[066] [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. | Zbl 0471.05038

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

[068] [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. | Zbl 0623.05043

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

[070] [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. | Zbl 0911.05043

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

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

[073] [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. | Zbl 0845.05076

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

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

[076] [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. | Zbl 0858.05049

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

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

[079] [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; MR501970.

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

[081] [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. | Zbl 0705.05016

[082] [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. | Zbl 0609.05057

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

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

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

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

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

[088] [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. | Zbl 0863.05045

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[103] [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:1<33::AID-JGT3>3.0.CO;2-L. | Zbl 0864.05037

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