Hostname: page-component-74656f9884-rdgjk Total loading time: 0 Render date: 2026-11-08T08:26:22.761Z Has data issue: false hasContentIssue false
  • English
  • Français

Triangle-Free Graphs with Large Degree

Published online by Cambridge University Press:  01 December 1997

C. C. CHEN ,
G. P. JIN  and
K. M. KOH
C. C. CHEN
Affiliation:
Department of Mathematics, National University of Singapore, Kent Ridge, Singapore 0511 and Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, UK; (e-mail: G.Jin@dpmms.cam.ac.uk)
G. P. JIN
Affiliation:
Department of Mathematics, National University of Singapore, Kent Ridge, Singapore 0511 and Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, UK; (e-mail: G.Jin@dpmms.cam.ac.uk)
K. M. KOH
Affiliation:
Department of Mathematics, National University of Singapore, Kent Ridge, Singapore 0511 and Department of Pure Mathematics and Mathematical Statistics, 16 Mill Lane, Cambridge CB2 1SB, UK; (e-mail: G.Jin@dpmms.cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

A graph G is called an H-type graph for some graph H if there is a mapping from V(G) to V(H) preserving edges. In this paper, we shall prove that: (1) every triangle-free graph G of order n with χ(G)[les ]3 and δ(G)>n/3 is of Fd-type for some d[ges ]1, where Fd is a certain d-regular triangle-free Hamiltonian Cayley graph of order 3d−1, (2) every triangle-free graph G of order n with χ(G)[ges ]4 and δ(G)>n/3 contains the Mycielski graph (see Figure 2) as a subgraph.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 4 , December 1997 , pp. 381 - 396
Copyright
1997 Cambridge University Press