4-kritické grafy bez trojúhelníků na toru a Kleinově lahvi

• Název práce v češtině: 4-kritické grafy bez trojúhelníků na toru a Kleinově lahvi
• Název v anglickém jazyce: 4-critical triangle-free graphs on torus and Klein bottle
• Klíčová slova: grafy, barevnost, plochy
• Klíčová slova anglicky: graph theory, graph coloring, surfaces
• Akademický rok vypsání: 2017/2018
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Informatický ústav Univerzity Karlovy (32-IUUK)
• Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.

Zásady pro vypracování

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.

Seznam odborné literatury

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

Předběžná náplň práce

Možné i jako základ diserační práce.