Gyárfás–Sumner gissning

Olöst problem i matematik :

Ger förbud mot både ett träd och en klick som inducerade subgrafer grafer med begränsat kromatiskt tal?

(fler olösta problem i matematik)

I grafteorin frågar Gyárfás –Sumner gissningen om, för varje träd $T$ och komplett graf ${\displaystyle K},$ graferna med varken $T$ eller $K$ som inducerade subgrafer kan färgas korrekt med endast ett konstant antal färger. På motsvarande sätt frågar den om de $T$ -fria graferna är $\chi$ -begränsade . Den är uppkallad efter András Gyárfás och David Sumner , som formulerade den självständigt 1975 respektive 1981. Det förblir obevisat.

I denna gissning är det inte möjligt att ersätta $T$ med en graf med cykler. Som Paul Erdős och András Hajnal har visat, finns det grafer med godtyckligt stora kromatiska tal och samtidigt godtyckligt stor omkrets . Genom att använda dessa grafer kan man få grafer som undviker alla fasta val av en cyklisk graf och klick (med mer än två hörn) som inducerade subgrafer, och överskrider alla fasta gränser för det kromatiska numret.

Gissningen är känd för att vara sann för vissa speciella val av $T$ , inklusive banor , stjärnor och träd med radie två. Det är också känt att för vilket träd som helst $T$ är graferna som inte innehåller en underavdelning av $T$$\chi$ -avgränsade.

externa länkar

• Grafer med ett förbjudet inducerat träd är chi-bounded , Open Problem Garden