Induced Subgraphs of Graphs With Large Chromatic Number. X. Holes of Specific Residue
Induced Subgraphs of Graphs With Large Chromatic Number. X. Holes of Specific Residue
复制标题
具有大色数的图的导出子图。
作者：
A. Scott;P. Seymour
图论中的大量研究涉及具有大色数的图的诱导子图，特别是必须发生哪些诱导循环。在本文中，我们统一并大幅扩展了之前多篇论文的结果，表明对于每个正整数 k，每个具有大色数的图都包含一个大的完全子图或所有长度模 k 的诱导循环。作为一个应用，我们证明了 1990 年代 Kalai 和 Meshulam 的两个猜想，将图的色数与其独立复形的同源性联系起来。
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.
DOI：
10.1016/j.jctb.2019.05.001
发表时间：
2017-01
期刊：
J. Comb. Theory, Ser. B
影响因子：
--
作者：
M. Chudnovsky;A. Scott;P. Seymour;S. Spirkl
通讯作者：
M. Chudnovsky;A. Scott;P. Seymour;S. Spirkl
Kalai-Meshulam猜想的证明
影响因子：
1
作者：
Chudnovsky, Maria;Scott, Alex;Seymour, Paul;Spirkl, Sophie
通讯作者：
Spirkl, Sophie