Scott's induced subdivision conjecture for maximal triangle-free graphs

2011/07/18 by Nicolas Bousquet, Bousquet, Nicolas, Stéphan Thomassé +1 · 1 citation
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1107.3491

arxiv created 2011/07/18 · arxiv updated 2011/07/19

Abstract

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

Cited by

• Largest dyadic dual VC-dimension of non-piercing families

Related

• Induced subdivisions and bounded expansion
• Small families under subdivision
• Unavoidable induced subgraphs forced by graphs with many vertices of prescribed properties
• Subdivisions of a large clique in C₆-free graphs
• Excluding induced subdivisions of the bull and related graphs