Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue

DOI10.1007/S00493-019-3804-YMaRDI QIDQ2288360zbMATH OpenOpenAlexFDO

Authors Alex Scott, Paul Seymour

Publication date 17 January 2020

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

chromatic numberclique numbercomplete subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Abstract: A large body of research in graph theory concerns the induced subgraphs of graphs with large chromatic number, and especially which induced cycles must occur. In this paper, we unify and substantially extend results from a number of previous papers, showing that, for every positive integer k, every graph with large chromatic number contains either a large complete subgraph or induced cycles of all lengths modulo k. As an application, we prove two conjectures of Kalai and Meshulam from the 1990's connecting the chromatic number of a graph with the homology of its independence complex.

Review text

In graph theory, researchers are very often concerned with induced subgraphs of graphs with large chromatic number, and especially, which induced cycles must occur. In this work, the authors unify and substantially extend results from a number of previous papers. It is shown that for every positive number \(k\) every graph with large chromatic number contains either a large complete subgraph or induced cycles of lengths modulo \(k\). In view of this, two conjectures of Kalai and Meshulam from the 1990's connecting the chromatic number of a graph with the homology of its independence complex are proved.

Recommendations

• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Induced subgraphs of graphs with large chromatic number. III: Long holes
• Induced subgraphs of graphs with large chromatic number. IV: Consecutive holes
• Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• Induced subgraphs of graphs with large chromatic number. VII: Gyárfás' complementation conjecture
• Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures
• A result on large induced subgraphs with prescribed residues in bipartite graphs
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings

Cited in

(20)

• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Induced subgraphs of graphs with large chromatic number. XIII. New brooms
• Detecting a long odd hole
• Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
• Pure pairs. II: Excluding all subdivisions of a graph
• From \(\chi\)- to \(\chi_p\)-bounded classes
• Proof of the Kalai-Meshulam conjecture
• Coloring graphs with no even hole \(\geqslant 6\): the triangle-free case
• The Erdős-Hajnal property for graphs with no fixed cycle as a pivot-minor
• scientific article; zbMATH DE number 1002021 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Homomorphism reconfiguration via homotopy
• Polynomial bounds for chromatic number VII. Disjoint holes
• Induced subgraphs of induced subgraphs of large chromatic number
• Graphs of large chromatic number
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Induced subdivisions in \(K_{s,s}\)-free graphs with polynomial average degree
• Vertex-minor-closed classes are -bounded
• Induced C₄-free subgraphs with large average degree
• The total Betti number of the independence complex of ternary graphs

This page was built for publication: Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue

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