PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2001 | 21 | 2 | 167-177
Tytuł artykułu

Gallai's innequality for critical graphs of reducible hereditary properties

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
21
Numer
2
Strony
167-177
Opis fizyczny
Daty
wydano
2001
otrzymano
2000-08-02
poprawiono
2001-05-09
Twórcy
autor
  • 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
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1141
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.