Tato práce se zabývá vrcholovým barvením grafu. V první kapitole jsou uvedeny možné aplikace barvení grafu. Ve druhé kapitole definujeme jednotlivá uvažovaná barvení - vlastní, p-distanční, pakovací, acyklické a seznamové barvení. Třetí kapitola, která je rozdělena na čtyři podkapitoly, je věnována známým výsledkům uvažovaných typů barvení jak pro obecné grafy, rovinné grafy, tak zejména pro speciální třídy grafů uvažovaných v této práci v rámci daných podkapitol. V jednotlivých podkapitolách věnujeme pozornost srovnání chromatických čísel jednotlivých typů barvení v rámci dané speciální třídy grafů - cesty, kružnice,
stromy, kaktusy. V poslední podkapitole věnované vrcholovému barvení kaktusů dokážeme tvrzení pro vlastní, acyklické a seznamové barvení a zároveň uvádíme hypotézy pro p-distanční a pakovací barvení subkubických kaktusů.
Annotation in English
This thesis deals with vertex colorings of a graph. In the first chapter there are possible applications of graph colorings. In the second chapter we define considered colorings - proper, p-distance, packing, acyclic and list colorings. Third chapter, which is splitted into four parts, is devoted to known results of the considered colorings of general graphs, planar graphs and for special classes of graphs considered in this thesis. In these chapters we focus on comparing chromatic numbers of considered types of colorings for given classes of graphs - paths, cycles, trees, cacti. In the last subchapter, which is devoted to vertex colorings of cacti, we prove theorems for the proper, the acyclic and the list coloring and we also state conjectures for the p-distance and the packing coloring of cacti.
Tato práce se zabývá vrcholovým barvením grafu. V první kapitole jsou uvedeny možné aplikace barvení grafu. Ve druhé kapitole definujeme jednotlivá uvažovaná barvení - vlastní, p-distanční, pakovací, acyklické a seznamové barvení. Třetí kapitola, která je rozdělena na čtyři podkapitoly, je věnována známým výsledkům uvažovaných typů barvení jak pro obecné grafy, rovinné grafy, tak zejména pro speciální třídy grafů uvažovaných v této práci v rámci daných podkapitol. V jednotlivých podkapitolách věnujeme pozornost srovnání chromatických čísel jednotlivých typů barvení v rámci dané speciální třídy grafů - cesty, kružnice,
stromy, kaktusy. V poslední podkapitole věnované vrcholovému barvení kaktusů dokážeme tvrzení pro vlastní, acyklické a seznamové barvení a zároveň uvádíme hypotézy pro p-distanční a pakovací barvení subkubických kaktusů.
Annotation in English
This thesis deals with vertex colorings of a graph. In the first chapter there are possible applications of graph colorings. In the second chapter we define considered colorings - proper, p-distance, packing, acyclic and list colorings. Third chapter, which is splitted into four parts, is devoted to known results of the considered colorings of general graphs, planar graphs and for special classes of graphs considered in this thesis. In these chapters we focus on comparing chromatic numbers of considered types of colorings for given classes of graphs - paths, cycles, trees, cacti. In the last subchapter, which is devoted to vertex colorings of cacti, we prove theorems for the proper, the acyclic and the list coloring and we also state conjectures for the p-distance and the packing coloring of cacti.
Barvení grafů je jednou z nejrozšířenějších oblastí teorie grafů. V této práci budeme uvažovat pouze barvení vrcholů grafu, kde základním typem barvení je úloha přiřadit všem vrcholům grafu přirozená čísla tak, aby žádné dva sousední vrcholy nebyly 'obarveny' stejným číslem. Cílem bakalářské práce je seznámit se i s dalšími typy vrcholových barvení grafů (acyklické, distanční, pakovací, seznamové) a porovnat jejich případné vztahy pro obecné grafy nebo pro speciální třídy grafů.
Research Plan
Barvení grafů je jednou z nejrozšířenějších oblastí teorie grafů. V této práci budeme uvažovat pouze barvení vrcholů grafu, kde základním typem barvení je úloha přiřadit všem vrcholům grafu přirozená čísla tak, aby žádné dva sousední vrcholy nebyly 'obarveny' stejným číslem. Cílem bakalářské práce je seznámit se i s dalšími typy vrcholových barvení grafů (acyklické, distanční, pakovací, seznamové) a porovnat jejich případné vztahy pro obecné grafy nebo pro speciální třídy grafů.
Recommended resources
R. Diestel, Graduate Texts in Mathematics: Graph Theory, Fourth Edition, Springer -Verlag Heidelberg, 2010, ISBN 978-3-642-14278-9.
F. Kramer, H. Kramer, A survey on the distance-colouring of graphs, Discrete
Mathematics 308 (2008), 422 - 426.
W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris, D. F. Rall, Broadcast Chromatic Numbers of Graphs, Ars Commbin. 86 (2008), 33-49.
Recommended resources
R. Diestel, Graduate Texts in Mathematics: Graph Theory, Fourth Edition, Springer -Verlag Heidelberg, 2010, ISBN 978-3-642-14278-9.
F. Kramer, H. Kramer, A survey on the distance-colouring of graphs, Discrete
Mathematics 308 (2008), 422 - 426.
W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris, D. F. Rall, Broadcast Chromatic Numbers of Graphs, Ars Commbin. 86 (2008), 33-49.