Hostname: page-component-586b7cd67f-r5fsc Total loading time: 0 Render date: 2024-11-28T17:16:43.208Z Has data issue: false hasContentIssue false
  • English
  • Français

Triangle-Free Graphs with High Minimal Degrees

Published online by Cambridge University Press:  12 September 2008

Guoping Jin
Guoping Jin
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, England
Get access Rights & Permissions [Opens in a new window]

Abstract

The main result of this paper gives a structure of a triangle-free graph of order n with minimal degree greater than 10n/29. This extends results given by Andrásfai et al. [1] and Häggkvist [6].

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 4 , December 1993 , pp. 479 - 490
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Andrásfai, B., Erdős, P. and Sós, V. T. (1974) On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Mathematics 8 205–218.CrossRefGoogle Scholar
[2]Bollobás, B. (1978) Extremal Graph Theory, Academic Press, London, 488 pp.Google Scholar
[3]Bollobás, B. (1979) Graph Theory – An Introductory Course, Graduate Texts in Mathematics 63, Springer-Verlag, New York-Heidelberg-Berlin, 177 pp.Google Scholar
[4]Erdԕs, P. and Simonovits, M. (1973) On a valence problem in extremal graph theory. Discrete Mathematics 5 323–334.CrossRefGoogle Scholar
[5]Grötzsch, H. (1959) Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss Z. Martin-Luther Univertität Halle-Wittenberg, Math.-Nat. Reihe 8 109–120.Google Scholar
[6]Häggkvist, R. (1982) Odd cycles of specified length in non-bipartite graphs. In: Bollobás, B. (ed.) Graph Theory. Annals of Discrete Mathematics 13 89–100.Google Scholar
[7]Jin, G. (submitted) Triangle-free four-chromatic graphs.Google Scholar
[8]Mycielski, J. (1955) Sur le coloriage des graphes. Colloq. Math. 3 161–162.CrossRefGoogle Scholar
[9]Turán, P. (1941) On an extremal problem in graph theory. Mat. Fiz. Lapok 48 436–452 (in Hungarian).Google Scholar