Varianty problému obarvení

• Název práce v češtině: Varianty problému obarvení
• Název v anglickém jazyce: Variants of the coloring problem
• Akademický rok vypsání: 2006/2007
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. RNDr. Jiří Fiala, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 06.10.2006
• Datum zadání: 06.10.2006
• Datum a čas obhajoby: 11.09.2007 00:00
• Datum odevzdání elektronické podoby: 11.09.2007
• Datum odevzdání tištěné podoby: 06.10.2006
• Datum proběhlé obhajoby: 11.09.2007
• Oponenti: prof. RNDr. Daniel Kráľ, Ph.D., DSc.

Zásady pro vypracování

Cílem práce je prozkoumat různé varianty problému obarvení (např. vybíravost, barvení podmíněné vzdáleností, apod.), především se zřetelem na různé třídy grafů, např. rovinné nebo vnějškově rovinné grafy. U daných problémů je možno se zaměřit jednak na existenční otázky daných obarvení, popř. na výpočetní složitost nalezení vhodného obarvení.

Seznam odborné literatury

T. Jensen and B. Toft. Graph Coloring Problems. John Wiley & Sons, New York, 1995.
N. Alon and M. Tarsi. Colorings and orientations of graphs. Combinatorica, 12:125-134, 1992.
M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman, 1979.
L. Kučera, Kombinatorické algoritmy, SNTL 1983, 1991.
časopisecká literatura dle doporučení vedoucího

Předběžná náplň práce

Práce se zabývá variantami problému obarvení (např. vybíravost, barvení podmíněné vzdáleností), vzhledem k různým třídám grafů.

Předběžná náplň práce v anglickém jazyce

The thesis considers various coloring problems (e.g. choosability, distance constrained coloring), with respect to various graph classes.