Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T10:58:15.233Z Has data issue: false hasContentIssue false
  • English
  • Français

Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs

Published online by Cambridge University Press:  21 March 2012

NICOLAS BOUSQUET  and
STÉPHAN THOMASSÉ
NICOLAS BOUSQUET
Affiliation:
Université Montpellier 2, CNRS, LIRMM, 161 Rue Ada, 34392 Montpellier, France (e-mail: bousquet@lirmm.fr)
STÉPHAN THOMASSÉ
Affiliation:
Laboratoire LIP (Université Lyon, CNRS, ENS Lyon, INRIA, UCBL), 46 Allée d'Italie, 69364 Lyon CEDEX 07, France (e-mail: stephan.thomasse@ens-lyon.fr)
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.

Scott conjectured in [6] that the class of graphs with no induced subdivision of a given graph is χ-bounded. We verify his conjecture for maximal triangle-free graphs.

Keywords

05C15

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 4 , July 2012 , pp. 512 - 514
Copyright
Copyright © Cambridge University Press 2012

References

[1]Bollobás, B. and Thomason, A. (1998) Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs. Europ. J. Combin. 19 883–887.CrossRefGoogle Scholar
[2]Ding, G., Seymour, P. and Winkler, P. (1994) Bounding the vertex cover number of a hypergraph. Combinatorica 14 23–34.CrossRefGoogle Scholar
[3]Gyárfás, A. (1987) Problems from the world surrounding perfect graphs. Zastos. Mat. XIX 413–441.Google Scholar
[4]Kim, J. (1995) The Ramsey number R(3, t) has order of magnitude t 2/log (t). Random Struct. Alg. 7 173–207.CrossRefGoogle Scholar
[5]Mader, W. (1967) Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen 174 265–268.CrossRefGoogle Scholar
[6]Scott, A. (1997) Induced trees in graphs of large chromatic number. J. Graph Theory 24 297–311.3.0.CO;2-J>CrossRefGoogle Scholar