Gallai's innequality for critical graphs of reducible hereditary properties

Peter Mihók; Riste Skrekovski

Discussiones Mathematicae Graph Theory (2001)

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

Abstract

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

How to cite

top

Peter 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. [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. [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. [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. [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. [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. [6] T. Gallai, Kritische Graphen I, Publ. Math. Inst. Hung. Acad. Sci. 8 (1963) 373-395. Zbl0144.23204
  7. [7] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley, New York, 1995). 
  8. [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. [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. [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. [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. [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. [13] P. Mihók, On the structure of the point arboricity critical graphs, Math. Slovaca 31 (1981) 101-108. Zbl0463.05042
  14. [14] R. Skrekovski, On the critical point-arboricity graphs, manuscript, 1998. 
  15. [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. [16] V.G. Vizing, Coloring the vertices of a graph in prescribed colours (in Russian), Diskret. Analiz 29 (1976) 3-10. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.