Gallai's innequality for critical graphs of reducible hereditary properties
Peter Mihók ; Riste Skrekovski
Discussiones Mathematicae Graph Theory, Tome 21 (2001), p. 167-177 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

In this paper Gallai’s inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let ₁,₂,...,ₖ (k ≥ 2) be additive induced-hereditary properties, =₁∘₂∘...∘ₖ and δ=∑i=1kδ(i). Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or G=Kδ+1. The generalization of Gallai’s inequality for -choice critical graphs is also presented.

Publié le : 2001-01-01
EUDML-ID : urn:eudml:doc:270179 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1141,
     author = {Peter Mih\'ok and Riste Skrekovski},
     title = {Gallai's innequality for critical graphs of reducible hereditary properties},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {21},
     year = {2001},
     pages = {167-177},
     zbl = {1002.05025},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1141}
}

Peter Mihók; Riste Skrekovski. Gallai's innequality for critical graphs of reducible hereditary properties. Discussiones Mathematicae Graph Theory, Tome 21 (2001) pp. 167-177. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1141/

[000] [1] G.A. Dirac, A theorem of R.L. Brooks and a conjecture of H. Hadwiger, Proc. London Math. Soc. 7 (1957) 161-195, doi: 10.1112/plms/s3-7.1.161. | Zbl 0077.17002

[001] [2] O.V. Borodin, A.V. Kostochka and B. Toft, Variable degeneracy: extensions of Brooks' and Gallai's theorems, Discrete Math. 214 (2000) 101-112, doi: 10.1016/S0012-365X(99)00221-6. | Zbl 0949.05029

[002] [3] M. Borowiecki, E. Drgas-Burchardt and P. Mihók, Generalized list colourings of graphs, Discuss. Math. Graph Theory 15 (1995) 185-193, doi: 10.7151/dmgt.1016. | Zbl 0845.05046

[003] [4] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, ed., Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68.

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

[005] [6] T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hung. Acad. Sci. 8 (1963) 373-395. | Zbl 0144.23204

[006] [7] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley, New York, 1995).

[007] [8] 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

[008] [9] A.V. Kostochka and M. Stiebitz, On the number of edges in colour-critical graphs and hypergraphs, Combinatorica 20 (2000) 521-530, doi: 10.1007/s004930070005. | Zbl 0996.05046

[009] [10] A.V. Kostochka and M. Stiebitz, A New Lower Bound on the Number of Edges in Colour-Critical Graphs and Hypergraphs, manuscript, 1999. | Zbl 1020.05028

[010] [11] M. Krivelevich, On the minimal number of edges in color-critical graphs, Combinatorica 17 (1997) 401-426, doi: 10.1007/BF01215921. | Zbl 0902.05025

[011] [12] M. Krivelevich, An improved bound on the minimal number of edges in color-critical graphs, Electronic J. Combin. 5 (1998) #R4. | Zbl 0885.05063

[012] [13] P. Mihók, On the structure of the point arboricity critical graphs, Math. Slovaca 31 (1981) 101-108. | Zbl 0463.05042

[013] [14] R. Skrekovski, On the critical point-arboricity graphs, manuscript, 1998.

[014] [15] C. Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory (B) 70 (1997) 67-100, doi: 10.1006/jctb.1996.1722. | Zbl 0883.05051

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