A survey of hereditary properties of graphs

 Access to full text

 Full (PDF)

1. [1] K. Appel and W. Haken, Every planar graph is four colourable, Illinois Jour. Math. 21(1977) 429-567. Zbl0387.05010
2. [2] G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely ${(m,k)}^{\tau }$-colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22. Zbl0870.05026
3. [3] G. Birkhoff, Lattice theory (AMS, New York, 1948). Zbl0033.10103
4. [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. Zbl0423.05021
5. [5] B. Bollobás and N. Sauer, Uniquely colourable graphs with large girth, Canad. J. Math. 28 (1976) no. 2 1340-1344; MR55#2632. Zbl0344.05115
6. [6] B. Bollobás and A.G. Thomason, Uniquely partitionable graphs, J. London Math. Soc. (2) 16 (1977) 403-410. Zbl0377.05038
7. [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. Zbl0866.05030
8. [8] J. A. Bondy and U. S. Murty, Graph theory with applications (American Elsevier Publishing Co., Inc., New York, 1976); MR54#117. Zbl1226.05083
9. [9] O. V. Borodin, On decomposition of graphs into degenerate subgraphs, Diskret. Analiz. 28(1976) 3-11. Zbl0425.05058
10. [10] O. V. Borodin, On acyclic colouring of planar graphs, Discrete Math.25(1979) 211-236, doi: 10.1016/0012-365X(79)90077-3. Zbl0406.05031
11. [11] M. Borowiecki, I. Broere and P. Mihók, Minimal reducible bounds for planar graphs (manuscript) 1997. Zbl0945.05022
12. [12] M. Borowiecki, I. Broere and P. Mihók, On generalized list colourings of graphs (manuscript) 1997. Zbl0903.05022
13. [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. Zbl0845.05046
14. [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. Zbl0961.05038
15. [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. Zbl0813.05061
16. [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. Zbl0958.05102
17. [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. [18] P. Borowiecki and J. Ivanco, P-bipartitions of minor hereditary properties Discussiones Mathematicae Graph Theory 17 (1997) 89-93. Zbl0914.05057
19. [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. Zbl0712.05024
20. [20] I. Broere, M. Frick and P. Mihók, On the order of uniquely partitionable graphs Discussiones Mathematicae Graph Theory 17 (1997) 115-125. Zbl0906.05058
21. [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). Zbl0902.05027
22. [22] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Phil. Soc. 37(1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
23. [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. Zbl0879.05029
24. [24] J. Bucko, P. Mihók and M. Voigt, Uniquely partitionable planar graphs (submitted) 1996. Zbl0957.05029
25. [25] S.A. Burr and M.S. Jacobson, On inequalities involving vertex partition parameter of graphs, Congr. Numerantium 70(1990) 159-170. 
26. [26] G. Chartrand, D. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, Journal of Combinatorial Theory (B) 10(1971) 12-41; MR44#2645. Zbl0223.05101
27. [27] G. Chartrand and J. P. Geller, Uniquely colourable planar graphs, J. Comb. Theory 6(1969) 271-278; MR39#2661. Zbl0175.50206
28. [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. Zbl0164.54201
29. [29] G. Chartrand and L. Lesniak, Graphs and digraphs (Wadsworth & Brooks/Cole, Monterey California, 1986). Zbl0666.05001
30. [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. Zbl0728.05050
31. [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. Zbl0596.05024
32. [32] L. J. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited (to appear). 
33. [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. Zbl0758.05050
34. [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. [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. [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. [37] Z. Filáková, P. Mihók and G. Semanišin, On maximal k-degenerate graphs (to appear in Mathematica Slovaca in 1997). 
38. [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. [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. Zbl0794.05029
40. [40] T. Gallai, Uber extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2(1959) 133 - 138 (German); MR24#A1222. Zbl0094.36105
41. [41] T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hung. Acad. Sci.8 (1963) 165 - 192 (German); MR32#5540. 
42. [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. Zbl0346.05110
43. [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). Zbl0411.68039
44. [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. Zbl0338.05120
45. [45] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94, doi: 10.1016/0012-365X(91)90166-Y. Zbl0742.05041
46. [46] R.L. Graham, B.L. Rothschild and J.H. Spencer, Ramsey theory (A Wiley-Interscience Publication, New York, 1980). 
47. [47] G. Gratzer, Universal algebra (D. van Nostrand and Co., 1968). 
48. [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. Zbl0312.05128
49. [49] B. Grunbaum, Acyclic colorings of planar graphs, Israel J. Math. 14(1973) 390-408, doi: 10.1007/BF02764716. Zbl0265.05103
50. [50] S. Gutner, The complexity of planar graph choosability, Discrete Math.159(1996) 119-130, doi: 10.1016/0012-365X(95)00104-5. Zbl0865.05066
51. [51] S.L. Hakimi, E. Schmeichel and J. Weinstein, Partitioning planar graphs into independent sets and forest, Congressus Numerantium 78(1990) 109-118. Zbl0862.05056
52. [52] F. Harary, S. T. Hedetniemi and R. W. Robinson, Uniquely colourable graphs, J. Comb. Theory 6(1969) 264-270; MR39#99. Zbl0175.50205
53. [53] S. T. Hedetniemi, Hereditary properties of graphs, J. Combin. Theory (B) 14(1973) 94-99; MR47#4861. Zbl0249.05116
54. [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. Zbl0548.05055
55. [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. Zbl0639.05023
56. [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. Zbl0709.05029
57. [57] T. R. Jensen and B. Toft, Graph colouring problems (Wiley-Interscience Publications, New York, 1995). Zbl0971.05046
58. [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. Zbl0593.05041
59. [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. Zbl0698.05048
60. [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. Zbl0871.05024
61. [61] J. Kratochvil and P. Mihók, Hom-properties are uniquely factorizable into irreducible factors (submitted). Zbl0949.05025
62. [62] J. Kratochvil, P. Mihók and G. Semanišin, Graphs maximal with respect to hom-properties (submitted). Zbl0905.05038
63. [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. Zbl0807.68055
64. [64] R. Lick and A. T. White, k-degenerate graphs, Canadian Journal of Mathematics 22(1970) 1082-1096; MR42#1715. Zbl0202.23502
65. [65] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar 1 (1966) 237-238; MR34#2442. Zbl0151.33401
66. [66] P. Mihók, The minimal reducible bounds for degenerate classes of graphs (manuscript). Zbl0995.05073
67. [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. Zbl0471.05038
68. [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. [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. Zbl0623.05043
70. [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. [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. Zbl0911.05043
72. [72] P. Mihók and G. Semanišin, On the chromatic number of reducible hereditary properties (submitted). Zbl1055.05061
73. [73] P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Mathematicae - Graph Theory 15(1995) 11-18; MR96c:05149. Zbl0829.05057
74. [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. Zbl0845.05076
75. [75] J. Mitchem, Maximal k-degenerate graphs, Utilitas Math. 11(1977) 101-106. Zbl0348.05109
76. [76] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3(1955) 161-162. 
77. [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. Zbl0858.05049
78. [78] J. Nesetril and V. Rodl, Partitions of vertices, Comment. Math. Univ. Carolinae 17(1976) no. 1 85-95; MR54#173. Zbl0344.05150
79. [79] J. Nieminen, Two bounds for the domination number of a graph, J. Inst. Math. Appl. 14(1974) 183-187; MR50#9708. Zbl0288.05124
80. [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. 
81. [81] O. Ore, Theory of graphs(Amer. Math. Soc. Colloq. Publ., vol. XXXVIII, AMS Providence, 1962); MR27#740. 
82. [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. Zbl0705.05016
83. [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. Zbl0609.05057
84. [84] G. Semanišin, On some variations of extremal graph problems Discussiones Mathematicae Graph Theory 17 (1997) 67-76. 
85. [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. [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. [87] M. Simonovits, Extremal graph problems with symmetrical extremal graphs. additional chromatical conditions, Discrete Mathematics 7(1974) 349-376; MR49#2459. Zbl0274.05113
88. [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. [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. Zbl0863.05045
90. [90] S.K. Stein, B-sets and planar graphs, Pacific J. Math. 37(1971) 217-224; MR46#5180. Zbl0194.56101
91. [91] L. Stockmeyer, Planar 3-colorability is polynomial complete, SIGACT News (ACM Publication) 5(1973) 19-25, doi: 10.1145/1008293.1008294. 
92. [92] C. Thomassen, Color-critical graphs on fixed surface, Report, Technical University of Denmark, Lyngby, 1995. 
93. [93] C. Thomassen, Decomposing a planar into degenerate graphs, J. Combin. Theory (B) 65(1995) 305-314, doi: 10.1006/jctb.1995.1057. Zbl0840.05070
94. [94] B. Toft, A survey of Hadwiger's conjecture, Preprints, Institut for Matematik og Datalogi, Odense Universitet, January 1996. 
95. [95] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48(1941) 436-452 (Hungarian); MR8,284j. 
96. [96] P. Turán, On the theory of graph, Colloquia Math. 3(1954) 19-30; MR15,476b. 
97. [97] Zs. Tuza, C₄-saturated graphs of minimum size, Acta Univ.Carolin.- Math. Phys. 30(1989) 161-167. Zbl0719.05040
98. [98] Zs. Tuza, Graph colorings with local constraints - a survey, Discussiones Mathematicae Graph Theory 17 (1997) (to appear). 
99. [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. [100] V. G. Vizing, Colouring the vertices of a graph in prescribed colours, Diskret. Analiz 29(1976) 3-10 (Russian). 
101. [101] M.L. Weaver and D.B. West Relaxed chromatic number of graphs, Graphs and Combinatorics 10(1994) 75-93, doi: 10.1007/BF01202473. Zbl0796.05036
102. [102] E. Welzl, Color families are dense, Theoretical Computer Sci. 17(1982) 29-41, doi: 10.1016/0304-3975(82)90129-3. Zbl0482.68063
103. [103] D. Woodall, Improper colorings of graphs, in: R. Nelson and R.J. Wilson, eds., Graph Colorings (Longman, New York, 1990) 45-64. 
104. [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. Zbl0864.05037
105. [105] A.A. Zykov, On some problems of linear complexes, Mat. Sbornik N. S.24(1949) 163-188. 

1. Ewa Kubicka, Grzegorz Kubicki, Kathleen A. McKeon, Chromatic Sums for Colorings Avoiding Monochromatic Subgraphs
2. Izak Broere, Peter Mihók, Hereditarnia
3. Alfonz Haviar, Roman Nedela, On varieties of graphs
4. Mariusz Hałuszczak, Pavol Vateha, On the completeness of decomposable properties of graphs
5. Piotr Borowiecki, Jaroslav Ivančo, 𝓟-bipartitions of minor hereditary properties
6. Wayne Goddard, Teresa Haynes, Debra Knisley, Hereditary domination and independence parameters
7. Amelie J. Berger, Peter Mihók, Prime ideals in the lattice of additive induced-hereditary graph properties
8. Peter Mihók, Janka Oravcová, Roman Soták, Generalized circular colouring of graphs
9. Piotr Borowiecki, On-line 𝓟-coloring of graphs
10. Gabriela Karafová, Generalized Fractional Total Colorings of Complete Graph