Английская Википедия:Gyárfás–Sumner conjecture

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Unsolved In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree <math>T</math> and complete graph <math>K</math>, the graphs with neither <math>T</math> nor <math>K</math> as induced subgraphs can be properly colored using only a constant number of colors. Equivalently, it asks whether the <math>T</math>-free graphs are <math>\chi</math>-bounded.Шаблон:R It is named after András Gyárfás and David Sumner, who formulated it independently in 1975 and 1981 respectively.Шаблон:R It remains unproven.Шаблон:R

In this conjecture, it is not possible to replace <math>T</math> by a graph with cycles. As Paul Erdős and András Hajnal have shown, there exist graphs with arbitrarily large chromatic number and, at the same time, arbitrarily large girth.Шаблон:R Using these graphs, one can obtain graphs that avoid any fixed choice of a cyclic graph and clique (of more than two vertices) as induced subgraphs, and exceed any fixed bound on the chromatic number.Шаблон:R

The conjecture is known to be true for certain special choices of <math>T</math>, including paths,Шаблон:R stars, and trees of radius two.Шаблон:R It is also known that, for any tree <math>T</math>, the graphs that do not contain any subdivision of <math>T</math> are <math>\chi</math>-bounded.Шаблон:R

External links

• Graphs with a forbidden induced tree are chi-bounded, Open Problem Garden