Induced subgraphs of graphs with large chromatic number. VI. Banana trees

DOI10.1016/J.JCTB.2020.01.004MaRDI QIDQ2200935zbMATH OpenOpenAlexFDO

Authors Alex Scott, Paul Seymour

Publication date 24 September 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.05597

zbMATH Keywords

treesgraph colouring\(\chi\)-boundedness

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15)

Abstract: We investigate which graphs H have the property that in every graph with bounded clique number and sufficiently large chromatic number, some induced subgraph is isomorphic to a subdivision of H. In an earlier paper, one of us proved that every tree has this property; and in another earlier paper with M. Chudnovsky, we proved that every cycle has this property. Here we give a common generalization. Say a banana is the union of a set of paths all with the same ends but otherwise disjoint. We prove that if H is obtained from a tree by replacing each edge by a banana then H has the property mentioned. We also find some other multigraphs with the same property.

Recommendations

• scientific article; zbMATH DE number 1002021
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Chromatic number and subtrees of graphs
• Induced subgraphs of graphs with large chromatic number. XII. Distant stars
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms

Cites work

• scientific article; zbMATH DE number 1002021 (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. III: Long holes
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Restricted frame graphs and a conjecture of Scott
• Triangle-free intersection graphs of line segments with large chromatic number

Cited in

(6)

• The parametrized complexity of the segment number
• Graphs of large chromatic number
• Improved bounds for colouring circle graphs
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• On the chromatic number of (P_{5},windmill)-free graphs
• Coloring polygon visibility graphs and their generalizations

This page was built for publication: Induced subgraphs of graphs with large chromatic number. VI. Banana trees

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