Grid representations of graphs and the chromatic number

• Název práce v češtině: Grid representations of graphs and the chromatic number
• Název v anglickém jazyce: Grid representations of graphs and the chromatic number
• Klíčová slova: grafové reprezentace, mřížka, barevnost grafů, rovina
• Klíčová slova anglicky: graph representations, grid, chromatic number, plane
• Akademický rok vypsání: 2010/2011
• Typ práce: diplomová práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. RNDr. Pavel Valtr, Dr.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 05.09.2011
• Datum zadání: 05.09.2011
• Datum potvrzení stud. oddělením: 03.10.2011
• Datum a čas obhajoby: 18.09.2012 10:00
• Datum odevzdání elektronické podoby: 02.08.2012
• Datum odevzdání tištěné podoby: 02.08.2012
• Datum proběhlé obhajoby: 18.09.2012
• Oponenti: prof. RNDr. Jan Kratochvíl, CSc.

Zásady pro vypracování

Prostudovat zadanou literaturu. Zkoumat reprezentace grafu s vrcholy umístěnými na mřížce v rovině nebo vícedimenzionálním prostoru, s žádným nebo malým počtem mřížkových bodů uvnitř každé hrany.
Zkoumat souvislost s barevností grafu.

Seznam odborné literatury

J. Matoušek: Lectures on Discrete Geometry, Springer 2002,
články v časopisech (bude průběžně upřesňováno).