Przypuszczenie Gyárfása-Sumnera

Nierozwiązany problem z matematyki :

Czy zakazanie zarówno drzewa, jak i kliki jako indukowanych podgrafów daje grafy o ograniczonej liczbie chromatycznej?

(więcej nierozwiązanych problemów z matematyki)

W teorii grafów hipoteza Gyárfása -Sumnera pyta, czy dla każdego drzewa i pełnego wykresu wykresy bez indukcji ani T { $ani$$K$$T},$ { $K}$ podgrafy można odpowiednio pokolorować przy użyciu tylko stałej liczby kolorów. Równoważnie pyta, czy $wykresy$ to ${\ displaystyle \ chi}$ -ograniczony . Jej nazwa pochodzi od Andrása Gyárfása i Davida Sumnera , którzy sformułowali ją niezależnie odpowiednio w 1975 i 1981 roku. Pozostaje nieudowodnione.

$jest$ możliwe zastąpienie z cyklami. Jak Paul Erdős i András Hajnal , istnieją grafy o dowolnie dużej liczbie chromatycznej i jednocześnie dowolnie dużym obwodzie . Korzystając z tych grafów, można uzyskać grafy, które unikają jakiegokolwiek ustalonego wyboru wykresu cyklicznego i kliki (z więcej niż dwóch wierzchołków) jako indukowanych podgrafów i przekraczają wszelkie ustalone granice liczby chromatycznej.

Wiadomo, że przypuszczenie jest prawdziwe w przypadku pewnych specjalnych wyborów, w tym ścieżek , gwiazd i drzew o promieniu dwóch. ${\ displaystyle T}$ Wiadomo również, że dla dowolnego $są$ wykresy $zawierają$ które nie podpodziału $ograniczone$ .

Linki zewnętrzne

• Grafy z zakazanym drzewem indukowanym są ograniczone chi , Open Problem Garden