3-Coloring Graphs on Torus
| Název práce v češtině: | 3-barevnost grafů na toru |
|---|---|
| Název v anglickém jazyce: | 3-Coloring Graphs on Torus |
| Klíčová slova: | barvení, grafy, torus |
| Klíčová slova anglicky: | coloring, graph, torus |
| Akademický rok vypsání: | 2015/2016 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Informatický ústav Univerzity Karlovy (32-IUUK) |
| Vedoucí / školitel: | prof. Mgr. Zdeněk Dvořák, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 23.02.2016 |
| Datum zadání: | 23.02.2016 |
| Datum potvrzení stud. oddělením: | 03.03.2016 |
| Datum a čas obhajoby: | 06.09.2017 09:00 |
| Datum odevzdání elektronické podoby: | 20.07.2017 |
| Datum odevzdání tištěné podoby: | 20.07.2017 |
| Datum proběhlé obhajoby: | 06.09.2017 |
| Oponenti: | doc. Mgr. Robert Šámal, Ph.D. |
| Zásady pro vypracování |
| 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). |
| Seznam odborné literatury |
| 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á |