Předmětem této práce je speciální třída neorientovaných grafů známých pod názvem distanční grafy. V této práci nejprve zrekapitulujeme již známé výsledky z oblasti vrcholového barvení distančních grafů, jejich hamiltonovských vlastností a dalších grafových barvení s přísnějšími podmínkami pro vzdálenosti vrcholů. Poté budeme prezentovat vlastní výsledky týkající se barvení distančních grafů G(1,t) pomocí barev, které vyžadují vzdálenost mezi stejně obarvenými vrcholy alespoň 1 nebo 2.
Anotace v angličtině
The subject of this diploma thesis is the special class of undirected graphs known as distance graphs. We first summarize known results on vertex colouring of distance graphs, their hamiltonian properties and other types of graph colourings with stricter requirements for vertex distances. Then we present our results on colouring of distance graphs G(1,t) with colours which require same-coloured vertices to be in a distance of at least 1 or 2.
Klíčová slova
Teorie grafů, distanční graf, grafové barvení, chromatické číslo, pakovací barvení, hamiltonovské vlastnosti
Předmětem této práce je speciální třída neorientovaných grafů známých pod názvem distanční grafy. V této práci nejprve zrekapitulujeme již známé výsledky z oblasti vrcholového barvení distančních grafů, jejich hamiltonovských vlastností a dalších grafových barvení s přísnějšími podmínkami pro vzdálenosti vrcholů. Poté budeme prezentovat vlastní výsledky týkající se barvení distančních grafů G(1,t) pomocí barev, které vyžadují vzdálenost mezi stejně obarvenými vrcholy alespoň 1 nebo 2.
Anotace v angličtině
The subject of this diploma thesis is the special class of undirected graphs known as distance graphs. We first summarize known results on vertex colouring of distance graphs, their hamiltonian properties and other types of graph colourings with stricter requirements for vertex distances. Then we present our results on colouring of distance graphs G(1,t) with colours which require same-coloured vertices to be in a distance of at least 1 or 2.
Klíčová slova
Teorie grafů, distanční graf, grafové barvení, chromatické číslo, pakovací barvení, hamiltonovské vlastnosti
Tato diplomová práce bude věnována studiu distančních grafů, především jejich chromatických parametrů.
Rovněž zde bude studována problematika hamiltonovských vlastností v distančních grafech.
Jedním z cílů pak bude výzkum v oblasti S-pakovacího barvení distančních grafů.
Přehledně zpracovat známé výsledky pro některá vybraná vrcholová barvení distančních grafů.
Shrnout známé výsledky pro hamiltonovské vlastnosti v distančních grafech.
Nalézt dolní a horní odhady pro S-pakovací chromatické číslo distančních grafů s dist. množinou \vyraz{D(1,t)
.
Zásady pro vypracování
Tato diplomová práce bude věnována studiu distančních grafů, především jejich chromatických parametrů.
Rovněž zde bude studována problematika hamiltonovských vlastností v distančních grafech.
Jedním z cílů pak bude výzkum v oblasti S-pakovacího barvení distančních grafů.
Přehledně zpracovat známé výsledky pro některá vybraná vrcholová barvení distančních grafů.
Shrnout známé výsledky pro hamiltonovské vlastnosti v distančních grafech.
Nalézt dolní a horní odhady pro S-pakovací chromatické číslo distančních grafů s dist. množinou \vyraz{D(1,t)
.
Seznam doporučené literatury
J. L. Gross, J. Yellen: Handbook of graph theory. Reading (Massachusetts): CRC Press LLC, 2004, ISBN 139781584880905.
C. Lowenstein, D. Rautenbach, R. Soták: On hamiltonian paths and cycles in sufficiently large distance graphs. DMTCS 16/1 (2014), n.1261.
R. B. Eggleton, P. Erdos, D. K. Skilton: Coloring the real line. J. Combin. Theor. Ser. B 39 (1985), 86-100.
A. Kemnitz, H. Kolberg: Coloring of integer distance graphs. Discrete Math. 191 (1998), 113-123.
Další literatura především časopiseckého charakteru bude upřesněna v průběhu práce.
Seznam doporučené literatury
J. L. Gross, J. Yellen: Handbook of graph theory. Reading (Massachusetts): CRC Press LLC, 2004, ISBN 139781584880905.
C. Lowenstein, D. Rautenbach, R. Soták: On hamiltonian paths and cycles in sufficiently large distance graphs. DMTCS 16/1 (2014), n.1261.
R. B. Eggleton, P. Erdos, D. K. Skilton: Coloring the real line. J. Combin. Theor. Ser. B 39 (1985), 86-100.
A. Kemnitz, H. Kolberg: Coloring of integer distance graphs. Discrete Math. 191 (1998), 113-123.
Další literatura především časopiseckého charakteru bude upřesněna v průběhu práce.