|
|
|
|||||||
| See by year | See by month | Jump to month | |||||||
Blázsik Zoltán: 1-metszet gráfok színezéseiről |
|
|||
|
|
||||
|
||||
| Egy H(V,E) hipergráf két hiperélére (e,f \in E) azt mondjuk, hogy 1-metszők, ha |e \cap f| = 1. A hipergráf H^{[1]}-el jelölt 1-metszet gráfjának a csúcsai megfelelnek a hipergráf hiperéleinek, és két hiperélt összekötünk H^{[1]}-ben, ha 1-metszők. 2015-ben Gyárfás et al belátták, hogy 3-uniform hipergráfok esetén ha az 1-metszet gráf k-színezhető, akkor maga a hipergráf is k-színezhető. Azt sejtették, hogy ez általánosítható l-uniform hipergráfokra l>3 esetén. Mi más irányban általánosítjuk az eredményüket, mert belátjuk, hogy az uniformitási feltétel elhagyható, tetszőleges hipergráfra teljesül ugyanez a konklúzió, amennyiben k=2. Azaz, ha egy tetszőleges H hipergráf 1-metszetgráfja páros, akkor a hipergráf is 2-színezhető. |
||||
Export Event JEvents v3.1.8 Stable Copyright © 2006-2013