# Gallai's innequality for critical graphs of reducible hereditary properties

Discussiones Mathematicae Graph Theory (2001)

- Volume: 21, Issue: 2, page 167-177
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPeter Mihók, and Riste Skrekovski. "Gallai's innequality for critical graphs of reducible hereditary properties." Discussiones Mathematicae Graph Theory 21.2 (2001): 167-177. <http://eudml.org/doc/270179>.

@article{PeterMihók2001,

abstract = {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.},

author = {Peter Mihók, Riste Skrekovski},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {additive induced-hereditary property of graphs; reducible property of graphs; critical graph; Gallai's Theorem; Gallai's inequality; critical graphs},

language = {eng},

number = {2},

pages = {167-177},

title = {Gallai's innequality for critical graphs of reducible hereditary properties},

url = {http://eudml.org/doc/270179},

volume = {21},

year = {2001},

}

TY - JOUR

AU - Peter Mihók

AU - Riste Skrekovski

TI - Gallai's innequality for critical graphs of reducible hereditary properties

JO - Discussiones Mathematicae Graph Theory

PY - 2001

VL - 21

IS - 2

SP - 167

EP - 177

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

LA - eng

KW - additive induced-hereditary property of graphs; reducible property of graphs; critical graph; Gallai's Theorem; Gallai's inequality; critical graphs

UR - http://eudml.org/doc/270179

ER -

## References

top- [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. Zbl0077.17002
- [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. Zbl0949.05029
- [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. Zbl0845.05046
- [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. Zbl0144.23204
- [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. Zbl0871.05024
- [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. Zbl0996.05046
- [10] A.V. Kostochka and M. Stiebitz, A New Lower Bound on the Number of Edges in Colour-Critical Graphs and Hypergraphs, manuscript, 1999. Zbl1020.05028
- [11] M. Krivelevich, On the minimal number of edges in color-critical graphs, Combinatorica 17 (1997) 401-426, doi: 10.1007/BF01215921. Zbl0902.05025
- [12] M. Krivelevich, An improved bound on the minimal number of edges in color-critical graphs, Electronic J. Combin. 5 (1998) #R4. Zbl0885.05063
- [13] P. Mihók, On the structure of the point arboricity critical graphs, Math. Slovaca 31 (1981) 101-108. Zbl0463.05042
- [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. Zbl0883.05051
- [16] V.G. Vizing, Coloring the vertices of a graph in prescribed colours (in Russian), Diskret. Analiz 29 (1976) 3-10.