Graf je 4-kritický, má-li barevnost 4, ale každý jeho podgraf má barevnost nejvýše 3. Jinak řečeno, graf lze obarvit 3 barvami, právě když neobsahuje 4-kritický podgraf. Pro grafy bez trojúhelníků nakreslené na nějaké pevné ploše existují strukturální výsledky popisující, jak takové 4-kritické podgrafy mohou vypadat. Tyto výsledky ale nedávají přesný seznam možných 4-kritických grafů (s výjimkou roviny a projektivní roviny). Cílem práce je přesně popsat 4-kritické grafy bez trojúhelníků nakreslitelné na torus či Kleinovu láhev.
References
Z. Dvořák, D. Kráľ, R. Thomas: Three-coloring triangle-free graphs on surfaces I-VI
Z. Dvořák, B. Lidický: 4-critical graphs on surfaces without contractible (<=4)-cycles
O. Borodin, Z. Dvořák, B. Lidický, A. Kostochka, M. Yancey: Planar 4-critical graphs with four triangles
