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/