Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Springer Verlag
2019
|
| _version_ | 1797081621940142080 |
|---|---|
| author | Scott, A Seymour, P |
| author_facet | Scott, A Seymour, P |
| author_sort | Scott, A |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T01:16:45Z |
| format | Journal article |
| id | oxford-uuid:8ef35282-8b11-4ad0-b049-0d77b75d415a |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:16:45Z |
| publishDate | 2019 |
| publisher | Springer Verlag |
| record_format | dspace |
| spelling | oxford-uuid:8ef35282-8b11-4ad0-b049-0d77b75d415a2022-03-26T23:01:05ZInduced subgraphs of graphs with large chromatic number. X. Holes of specific residueJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:8ef35282-8b11-4ad0-b049-0d77b75d415aSymplectic Elements at OxfordSpringer Verlag2019Scott, ASeymour, PA 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. |
| spellingShingle | Scott, A Seymour, P Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue |
| title | Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue |
| title_full | Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue |
| title_fullStr | Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue |
| title_full_unstemmed | Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue |
| title_short | Induced subgraphs of graphs with large chromatic number. X. Holes of specific residue |
| title_sort | induced subgraphs of graphs with large chromatic number x holes of specific residue |
| work_keys_str_mv | AT scotta inducedsubgraphsofgraphswithlargechromaticnumberxholesofspecificresidue AT seymourp inducedsubgraphsofgraphswithlargechromaticnumberxholesofspecificresidue |