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

DOI10.1016/J.JCTB.2020.01.004zbMATH Open1448.05145arXiv1701.05597OpenAlexW3003733317MaRDI QIDQ2200935FDOQ2200935

Alex Scott, Paul Seymour

Publication date: 24 September 2020

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted frame graphs and a conjecture of Scott
• Triangle-free intersection graphs of line segments with large chromatic number
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Induced subgraphs of graphs with large chromatic number. III: Long holes

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)