Geodesic
Gallai's innequality for critical graphs of reducible hereditary properties
Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 167-177.

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

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=1^k δ(_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.
Keywords: additive induced-hereditary property of graphs, reducible property of graphs, critical graph, Gallai's Theorem 
@article{DMGT_2001_21_2_a2,
     author = {Mih\'ok, Peter and Skrekovski, Riste},
     title = {Gallai's innequality for critical graphs of reducible hereditary properties},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {167--177},
     publisher = {mathdoc},
     volume = {21},
     number = {2},
     year = {2001},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a2/}
}
TY  - JOUR
AU  - Mihók, Peter
AU  - Skrekovski, Riste
TI  - Gallai's innequality for critical graphs of reducible hereditary properties
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2001
SP  - 167
EP  - 177
VL  - 21
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a2/
LA  - en
ID  - DMGT_2001_21_2_a2
ER  - 
%0 Journal Article
%A Mihók, Peter
%A Skrekovski, Riste
%T Gallai's innequality for critical graphs of reducible hereditary properties
%J Discussiones Mathematicae. Graph Theory
%D 2001
%P 167-177
%V 21
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a2/
%G en
%F DMGT_2001_21_2_a2
Mihók, Peter; Skrekovski, Riste. Gallai's innequality for critical graphs of reducible hereditary properties. Discussiones Mathematicae. Graph Theory, Tome 21 (2001) no. 2, pp. 167-177. http://geodesic.mathdoc.fr/item/DMGT_2001_21_2_a2/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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