Steinerovská barvení kubických grafů
| Název práce v češtině: | Steinerovská barvení kubických grafů |
|---|---|
| Název v anglickém jazyce: | Steiner coloring of cubic graphs |
| Klíčová slova: | kubický graf, hranové barvení, Steinerův systém trojic, Fanova rovina, Steinerovské obarvení, Fanovo obarvení |
| Klíčová slova anglicky: | cubic graph, edge coloring, Steiner triple system, Fano plane, Steiner coloring, Fano coloring |
| Akademický rok vypsání: | 2015/2016 |
| Typ práce: | diplomová práce |
| Jazyk práce: | češ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í: | 31.03.2016 |
| Datum zadání: | 01.04.2016 |
| Datum potvrzení stud. oddělením: | 22.04.2016 |
| Datum a čas obhajoby: | 15.09.2017 00:00 |
| Datum odevzdání elektronické podoby: | 20.07.2017 |
| Datum odevzdání tištěné podoby: | 21.07.2017 |
| Datum proběhlé obhajoby: | 15.09.2017 |
| Oponenti: | doc. Mgr. Robert Šámal, Ph.D. |
| Zásady pro vypracování |
| Cílem práce je podat přehled o známých výsledcích o Steinerovském barvení kubických grafů. Porozumění strukturálním vlastnostem by mělo být klíčem k určení výpočetní složitosti problémů souvisejících s existencí obarvení. Je známo, že uvedený problém existence Steinerovském barvení kubických grafů je v obecném případě NP-těžký, proto je vhodné dále studovat jeho zúžení na specifické třídy grafů. Alternativně lze zkoumat i barvení pomocí obecnějších blokových schémat, než jsou Steinerovy systémy trojic. |
| Seznam odborné literatury |
| T. R. Jensen, B. Toft: Graph coloring problems, John Wiley & Sons, 1995.
R. G. Downey, M. R. Fellows: Parameterized Complexity, Springer-Verlag, 1999. M. R. Garey, D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman (1979) Grannell, Mike; Griggs, Terry; Knor, Martin; Škoviera, Martin: A Steiner triple system which colors all cubic graphs. J. Graph Theory 46, No. 1, 15-24 (2004). Li, (Ben) Pak Ching; Toulouse, Michel: Some NP-completeness results on partial Steiner triple systems and parallel classes. Ars Comb. 80, 45-51 (2006). další časopisecká literatura dle doporučení školitele |