Restricted frame graphs and a conjecture of Scott

MaRDI QIDQ252837zbMATH OpenFDO

Authors J. Chalopin, L. Esperet, Zhentao Li, P. Ossona de Mendez

Publication date 4 March 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.0338, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p30

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chi-boundednesschromatic numberintersection graphsScott's conjecturesubdivisions

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Structural characterization of families of graphs (05C75)

Abstract: Scott proved in 1997 that for any tree $T$, every graph with bounded clique number which does not contain any subdivision of $T$ as an induced subgraph has bounded chromatic number. Scott also conjectured that the same should hold if $T$ is replaced by any graph $H$. Pawlik et al. recently constructed a family of triangle-free intersection graphs of segments in the plane with unbounded chromatic number (thereby disproving an old conjecture of ErdH{o}s). This shows that Scott's conjecture is false whenever $H$ is obtained from a non-planar graph by subdividing every edge at least once. It remains interesting to decide which graphs $H$ satisfy Scott's conjecture and which do not. In this paper, we study the construction of Pawlik et al. in more details to extract more counterexamples to Scott's conjecture. For example, we show that Scott's conjecture is false for any graph obtained from $K_4$ by subdividing every edge at least once. We also prove that if $G$ is a 2-connected multigraph with no vertex contained in every cycle of $G$, then any graph obtained from $G$ by subdividing every edge at least twice is a counterexample to Scott's conjecture.

Recommendations

• Invariants of framed graphs and the Kadomtsev-Petviashvili hierarchy
• Scott's induced subdivision conjecture for maximal triangle-free graphs
• Frame matroids and biased graphs
• `Restricted' closed graph theorems
• A graph-theoretic approach to a conjecture of Dixon and Pressman
• On Hadwiger conjecture for certain families of graphs with restricted number of cycles
• Restricted triangulation on circulant graphs
• Graphs with asymptotically invariant degree sequences under restriction
• On monochromatic frames in graphs
• scientific article; zbMATH DE number 3977950

Cites work

• Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors
• Graph Theory and Probability
• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• scientific article; zbMATH DE number 4183452 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• On graphs with no induced subdivision of \(K_4\)
• Sur le coloriage des graphs
• Triangle-free geometric intersection graphs with large chromatic number
• Triangle-free geometric intersection graphs with no large independent sets
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(17)

• Chromatic number of ISK4-free graphs
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Induced subgraphs of graphs with large chromatic number. VI. Banana trees
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Burling graphs revisited. I: New characterizations
• Scott's induced subdivision conjecture for maximal triangle-free graphs
• Treewidth versus clique number. I: Graph classes with a forbidden structure
• Burling graphs, chromatic number, and orthogonal tree-decompositions
• Burling graphs, chromatic number, and orthogonal tree-decompositions
• Triangle‐free graphs with large chromatic number and no induced wheel
• The chromatic number of {ISK4, diamond, bowtie}‐free graphs
• Some remarks on graphs with no induced subdivision of \(K_4\)
• Burling graphs revisited. II: Structure
• Burling graphs revisited. III: Applications to \(\chi \)-boundedness
• Graphs of large chromatic number
• Chi-boundedness of graphs containing no cycles with k chords
• A survey of degree-boundedness

This page was built for publication: Restricted frame graphs and a conjecture of Scott

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q252837)