Coloring triangle-free graphs on the torus

• Thesis title in Czech: Barvení grafů bez trojúhelníků na toru
• Thesis title in English: Coloring triangle-free graphs on the torus
• Key words: toroidalni|graf|3-obarvitelnost|algoritmus|implementace
• English key words: toroidal|graph|3-colorability|algorithm|implementation
• Academic year of topic announcement: 2021/2022
• Thesis type: Bachelor's 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: 05.11.2021
• Date of assignment: 05.11.2021
• Confirmed by Study dept. on: 19.11.2021
• Date and time of defence: 12.09.2022 09:00
• Date of electronic submission: 21.07.2022
• Date of submission of printed version: 21.07.2022
• Date of proceeded defence: 12.09.2022
• Opponents: doc. Mgr. Robert Šámal, Ph.D.

Guidelines

Pekárek and Dvořák (2021) proposed a linear-time algorithm to decide 3-colorability of triangle-free graphs drawn on the torus. The goal of the thesis is to efficiently implement this algorithm and to evaluate it (relatively to non-specialized 3-coloring algorithms for general graphs).

References

Zdeněk Dvořák, Jakub Pekárek: Coloring near-quadrangulations of the cylinder and the torus. Eur. J. Comb. 93: 103258 (2021)
Bojan Mohar, Carsten Thomassen: Graphs on surfaces