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ő.