Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures

DOI10.1016/J.JCTB.2016.01.003zbMATH Open1332.05053arXiv1411.6465OpenAlexW281717368MaRDI QIDQ256991FDOQ256991

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour 

Publication date: 14 March 2016

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

Abstract: Gyarfas conjectured in 1985 that for all $k$, $l$, every graph with no clique of size more than $k$ and no odd hole of length more than $l$ has chromatic number bounded by a function of $k$ and $l$. We prove three weaker statements: (1) Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five; (2) For all $l$, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than $l$; (3) For all $k$, $l$, every graph with no clique of size more than $k$ and sufficiently large chromatic number contains either a 5-hole or a hole of length more than $l$.

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

Recommendations

• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Induced cycles and chromatic number
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
• Induced subgraphs of graphs with large chromatic number. III: Long holes

zbMATH Keywords

\(\chi\)-boundedcolouringholesinduced subgraph

Mathematics Subject Classification ID

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

Cites Work

• Induced cycles and chromatic number
• Title not available (Why is that?)

Cited In (22)

• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Some remarks on graphs with no induced subdivision of \(K_4\)
• Characterization of forbidden subgraphs for bounded star chromatic number
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Induced subgraphs of graphs with large chromatic number. IX: Rainbow paths
• A dichotomy theorem for circular colouring reconfiguration
• The chromatic number of {ISK4, diamond, bowtie}‐free graphs
• Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
• Coloring curves that cross a fixed curve
• Polynomial bounds for chromatic number VII. Disjoint holes
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
• Scott's induced subdivision conjecture for maximal triangle-free graphs
• A note on a conjecture of Gy\'arf\'as
• Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
• A note on induced subtrees and chromatic number of graphs
• Coloring graphs without fan vertex-minors and graphs without cycle pivot-minors
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• A survey of \(\chi\)-boundedness
• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
• A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number

This page was built for publication: Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures

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