| dbo:abstract
|
- 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 .A sejtés nevét Gyárfás Andrásról és kapta, akik egymástól függetlenül 1975-ben, illetve 1981-ben megfogalmazták. Jelenleg bizonyítatlan. 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. 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. A sejtést bizonyították néhány speciálisan megválasztott -re, így útgráfokra, csillagokra és kettő sugarú fákra.Ismert az is, hogy azok a gráfok, melyek nem tartalmaznak bármely konkrét fát felosztásként, -korlátosak. (hu)
- 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 .A sejtés nevét Gyárfás Andrásról és kapta, akik egymástól függetlenül 1975-ben, illetve 1981-ben megfogalmazták. Jelenleg bizonyítatlan. 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. 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. A sejtést bizonyították néhány speciálisan megválasztott -re, így útgráfokra, csillagokra és kettő sugarú fákra.Ismert az is, hogy azok a gráfok, melyek nem tartalmaznak bármely konkrét fát felosztásként, -korlátosak. (hu)
|
