DMGT

Discussiones Mathematicae Graph Theory 21(1) (2001) 167-177
DOI: https://doi.org/10.7151/dmgt.1141

GALLAI'S INNEQUALITY FOR CRITICAL GRAPHS OF REDUCIBLE HEREDITARY PROPERTIES

Peter Mihók

Mathematical Institute of Slovak Academy of Sciences
Gresákova 6, 040 01 Košice, Slovakia
and
Faculty of Economics, Technical University
B. Nemcovej 32, 040 01 Košice, Slovakia
e-mail: mihokp@tuke.sk

Riste Skrekovski

Departement of Mathematics University of Ljubljana
Jadranska 19, 1111 Ljubljana, Slovenia
e-mail: skreko@fmf.uni-lj.si

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 P₁, P₂, …,P_k (k ≥ 2) be additive induced-hereditary properties, ℜ = P₁ º P₂ º… ºP_k and δ = ∑_{i = 1}^k δ(P_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 ℜ = O² or G = K_δ+1. The generalization of Gallai's inequality for P-choice critical graphs is also presented.

Keywords: additive induced-hereditary property of graphs, reducible property of graphs, critical graph, Gallai's Theorem.

2000 Mathematics Subject Classification: 05C15, 05C75.

References

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

Received 2 August 2000
Revised 9 May 2001