Gallai's innequality for critical graphs of reducible hereditary properties

• Autorzy: Peter Mihók , Riste Skrekovski
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C75: Structural characterization of families of graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2001
• Tom: 21
• Numer: 2
• Strony: 167-177

Daty

wydano

2001

otrzymano

2000-08-02

poprawiono

2001-05-09

Twórcy

autor

Peter Mihók

• 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

autor

Riste Skrekovski

• Departement of Mathematics University of Ljubljana, Jadranska 19, 1111 Ljubljana, Slovenia

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1141