Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-23T14:16:47.364Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  21 March 2012

NICOLAS BOUSQUET
Affiliation:
Université Montpellier 2, CNRS, LIRMM, 161 Rue Ada, 34392 Montpellier, France (e-mail: [email protected])
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: [email protected])

Abstract

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

Type
Paper
Copyright
Copyright © Cambridge University Press 2012

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]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 883887.CrossRefGoogle Scholar
[2]Ding, G., Seymour, P. and Winkler, P. (1994) Bounding the vertex cover number of a hypergraph. Combinatorica 14 2334.CrossRefGoogle Scholar
[3]Gyárfás, A. (1987) Problems from the world surrounding perfect graphs. Zastos. Mat. XIX 413441.Google Scholar
[4]Kim, J. (1995) The Ramsey number R(3, t) has order of magnitude t 2/log (t). Random Struct. Alg. 7 173207.CrossRefGoogle Scholar
[5]Mader, W. (1967) Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen 174 265268.CrossRefGoogle Scholar
[6]Scott, A. (1997) Induced trees in graphs of large chromatic number. J. Graph Theory 24 297311.3.0.CO;2-J>CrossRefGoogle Scholar