ArticleOriginal scientific text
Title
Gallai's innequality for critical graphs of reducible hereditary properties
Authors 1, 2, 3
Affiliations
- Mathematical Institute of Slovak Academy of Sciences, Gresákova 6, 040 01 Košice, Slovakia
- Faculty of Economics, Technical University, B. Nĕmcovej 32, 040 01 Košice, Slovakia
- Departement of Mathematics University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia
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 . 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 . 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
Bibliography
- 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.
- 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.
- 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.
- 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.
- 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.
- T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hung. Acad. Sci. 8 (1963) 373-395.
- T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley, New York, 1995).
- 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.
- 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.
- A.V. Kostochka and M. Stiebitz, A New Lower Bound on the Number of Edges in Colour-Critical Graphs and Hypergraphs, manuscript, 1999.
- M. Krivelevich, On the minimal number of edges in color-critical graphs, Combinatorica 17 (1997) 401-426, doi: 10.1007/BF01215921.
- M. Krivelevich, An improved bound on the minimal number of edges in color-critical graphs, Electronic J. Combin. 5 (1998) #R4.
- P. Mihók, On the structure of the point arboricity critical graphs, Math. Slovaca 31 (1981) 101-108.
- R. Skrekovski, On the critical point-arboricity graphs, manuscript, 1998.
- C. Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory (B) 70 (1997) 67-100, doi: 10.1006/jctb.1996.1722.
- V.G. Vizing, Coloring the vertices of a graph in prescribed colours (in Russian), Diskret. Analiz 29 (1976) 3-10.