Thesis (Selection of subject)Thesis (Selection of subject)(version: 368)
Thesis details
   Login via CAS
4-kritické grafy bez trojúhelníků na toru a Kleinově lahvi
Thesis title in Czech: 4-kritické grafy bez trojúhelníků na toru a Kleinově lahvi
Thesis title in English: 4-critical triangle-free graphs on torus and Klein bottle
Key words: grafy, barevnost, plochy
English key words: graph theory, graph coloring, surfaces
Academic year of topic announcement: 2017/2018
Thesis type: diploma thesis
Thesis language: čeština
Department: Computer Science Institute of Charles University (32-IUUK)
Supervisor: prof. Mgr. Zdeněk Dvořák, Ph.D.
Author:
Guidelines
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
Preliminary scope of work
Možné i jako základ diserační práce.
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html