3-Coloring Graphs on Torus

• Thesis title in Czech: 3-barevnost grafů na toru
• Thesis title in English: 3-Coloring Graphs on Torus
• Key words: barvení, grafy, torus
• English key words: coloring, graph, torus
• Academic year of topic announcement: 2015/2016
• Thesis type: diploma thesis
• Thesis language: angličtina
• Department: Computer Science Institute of Charles University (32-IUUK)
• Supervisor: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 23.02.2016
• Date of assignment: 23.02.2016
• Confirmed by Study dept. on: 03.03.2016
• Date and time of defence: 06.09.2017 09:00
• Date of electronic submission: 20.07.2017
• Date of submission of printed version: 20.07.2017
• Date of proceeded defence: 06.09.2017
• Opponents: doc. Mgr. Robert Šámal, Ph.D.

Guidelines

The famous Grötzsch theorem stating that every planar triangle-free graph is 3-colorable motivates the study of the problem on other surfaces. The first surface for that the complete characterization of non-3-colorable triangle-free graphs is not known is torus. The goal of the thesis is to fill in this gap and to provide such a characterization (at least a partial one).

References

Bojan Mohar and Carsten Thomassen: Graphs on surfaces, Johns Hopkins University Press, 2001.
C. Thomassen: Grötzsch′s 3-Color Theorem and Its Counterparts for the Torus and the Projective Plane, Journal of Combinatorial Theory, Series B 62 (2), 1994, 268-279.
Zdeněk Dvořák, Bernard Lidický: 4-Critical Graphs on Surfaces Without Contractible (<=4)-Cycles. SIAM J. Discrete Math. 28(1), 2014, 521-552.

další časopisecká