Barevnost grafů na plochách

• Název práce v češtině: Barevnost grafů na plochách
• Název v anglickém jazyce: Coloring graphs on surfaces
• Klíčová slova anglicky: graph, coloring, surfaces
• Akademický rok vypsání: 2010/2011
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. Mgr. Zdeněk Dvořák, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 30.09.2010
• Datum zadání: 01.10.2010
• Datum a čas obhajoby: 07.09.2011 09:00
• Datum odevzdání elektronické podoby: 03.08.2011
• Datum odevzdání tištěné podoby: 05.08.2011
• Datum proběhlé obhajoby: 07.09.2011
• Oponenti: doc. RNDr. Jiří Fiala, Ph.D.

Zásady pro vypracování

Student se seznámí s výsledky a metodami v oblasti barvení rovinných grafů a grafů na plochách. Získané poznatky se pokusí aplikovat na řešení některého z otevřených problémů v této oblasti, například problému barevnosti eulerovských triangulací ploch.

Seznam odborné literatury

T. R. Jensen, B. Toft: Graph Coloring Problems, Wiley-Interscience, 1994.
J. Hutchinson, B. Richter, P. Seymour: Colouring eulerian triangulations, J. Combinatorial Theory, Ser. B 84 (2002), 225-239.
A. Nakamoto: 5-Chromatic even triangulations on surfaces, Discrete Mathematics 308 (2008), 2571-2580.
Z. Dvorak, D. Kral, R. Thomas: Three-coloring triangle-free graphs on surfaces, manuscript.