Gyárfás–Sumner-sejtés
 |
A matematika megoldatlan problémája: Az egy adott fát és egy adott klikket feszített részgráfként nem tartalmazó gráfok kromatikus száma korlátos-e? (A matematika további megoldatlan problémái)
|
A matematika, azon belül a gráfelmélet területén a Gyárfás–Sumner-sejtés azt állítja, hogy tetszőleges fát és teljes gráfot választva, a feszített részgráfként sem -t, sem -t nem tartalmazó gráfok konstans számú színnel jól színezhetők. Ezzel ekvivalens megfogalmazás szerint, a - és -mentes gráfok -korlátosak.[1] A sejtés nevét Gyárfás Andrásról és David Sumnerről kapta, akik egymástól függetlenül 1975-ben, illetve 1981-ben megfogalmazták.[2][3] Jelenleg bizonyítatlan.[4]
A sejtésben nem lehetséges -t kört tartalmazó gráfra cserélni. Ahogy Erdős Pál és Hajnal András megmutatták, léteznek tetszőlegesen magas kromatikus számú, ugyanakkor tetszőlegesen nagy girthű háromszögmentes gráfok.[5] Ezen gráfok felhasználásával előállíthatók olyan gráfok, amik elkerülnek bármely fixen választott, kört tartalmazó gráfot és (2 csúcsnál nagyobb) klikket feszített részgráfként, de tetszőlegesen választott értéknél magasabb a kromatikus számuk.[1]
A sejtést bizonyították néhány speciálisan megválasztott -re, így útgráfokra,[6] csillagokra és kettő sugarú fákra.[7] Ismert az is, hogy azok a gráfok, melyek nem tartalmaznak bármely konkrét fát felosztásként, -korlátosak.[1]
Fordítás
szerkesztés- Ez a szócikk részben vagy egészben a Gyárfás–Sumner conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
szerkesztés- ↑ a b c Scott, A. D. (1997), "Induced trees in graphs of large chromatic number", Journal of Graph Theory 24 (4): 297–311, DOI 10.1002/(SICI)1097-0118(199704)24:4<297::AID-JGT2>3.3.CO;2-X
- ↑ Gyárfás, A. (1975), "On Ramsey covering-numbers", Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, vol. 10, Colloq. Math. Soc. János Bolyai, Amsterdam: North-Holland, pp. 801–816
- ↑ Sumner, D. P. (1981), "Subtrees of a graph and the chromatic number", The theory and applications of graphs (Kalamazoo, Mich., 1980), Wiley, New York, pp. 557–576
- ↑ Chudnovsky, Maria & Seymour, Paul (2014), "Extending the Gyárfás-Sumner conjecture", Journal of Combinatorial Theory, Series B 105: 11–16, DOI 10.1016/j.jctb.2013.11.002
- ↑ Erdős, P. & Hajnal, A. (1966), "On chromatic number of graphs and set-systems", Acta Mathematica Academiae Scientiarum Hungaricae 17: 61–99, doi:10.1007/BF02020444, <https://users.renyi.hu/~p_erdos/1966-07.pdf>
- ↑ Gyárfás, A. (1987), "Problems from the world surrounding perfect graphs", Zastosowania Matematyki 19 (3-4): 413–441 (1988)
- ↑ Kierstead, H. A. & Penrice, S. G. (1994), "Radius two trees specify χ-bounded classes", Journal of Graph Theory 18 (2): 119–129, DOI 10.1002/jgt.3190180203
További információk
szerkesztés- Graphs with a forbidden induced tree are chi-bounded, Open Problem Garden