Induced cycles and chromatic number (Q1306304): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Q222637 / rank | |||
Property / reviewed by | |||
Property / reviewed by: Hian Poh Yap / rank | |||
Property / author | |||
Property / author: Alexander D. Scott / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Hian Poh Yap / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1998.1894 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2167467023 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4063176 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5749319 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Induced subtrees in graphs of large chromatic number / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Radius two trees specify χ‐bounded classes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On-Line Coloring and Recursive Graph Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applications of hypergraph coloring to coloring graphs not inducing certain trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3129824 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3932997 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:28, 29 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Induced cycles and chromatic number |
scientific article |
Statements
Induced cycles and chromatic number (English)
0 references
20 December 1999
0 references
The author proves that for any pair of positive integers \(r\) and \(s\), there exists an integer \(N(r,s)\) such that every graph with chromatic number at least \(N(r,s)\) contains either the complete graph \(K_r\) or an induced odd cycle of length at least 5 or an induced cycle of length at least \(s\). This result is a weakened version of two conjectures made by A. Gyárfás (1985) which are related to the well-known strong perfect graph conjecture as well as the Gyárfás-Sumner conjecture (1973 and 1981). Several similar/related problems had been studied before by A. Gyárfás, H. A. Kierstead, S. G. Penrice, D. P. Sumner, E. Szemeredi, W. T. Trotter and Zs. Tuza.
0 references
chromatic number
0 references
induced cycle
0 references