|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (vedoucí práce) ; Sereni, Jean Sébastien (oponent) ; Fiala, Jiří (oponent)
V práci studujeme čtyři problémy ze strukturální teorie grafů. Nejprve se zabýváme strukturou grafů které mají nikde nenulový 5-tok. Podáme charakteri- zaci takových grafů pomocí existence (1, 2)−faktorů. Ve druhé části zavedeme nový typ dekorace vrcholů grafu, kterému říkáme aditivní barvení. Aditivní barvení je injektivní barvení s omezeními danými grafem. Studujeme strukturu grafů které mají tuto dekoraci, a související algoritmické otázky. Ve třetí časti studujeme hypotézu kterou formuloval před asi dvaceti lety R. Stanley: je pravda, že U-polynom rozlišuje neizomorfní stromy? Dokážeme tuto hypotézu pro stromy- housenky bez vrcholů stupně dva. O tento výsledek se v minulých letech snažila řada vědců, například S. Noble. Ve čtvrté části studujeme strukturu nekonečných grafů které mají uplný graf jako minor nebo topologický minor. Klíčová slova: graf, nikde nenulový tok, faktor grafu, barvení grafů, izomorfismus grafů, strom, U-polynom, minor, topologický minor.
|
|
|
Structural Graph Theory
Zamora, José ; Loebl, Martin (vedoucí práce) ; Sereni, Jean Sébastien (oponent) ; Fiala, Jiří (oponent)
V práci studujeme čtyři problémy ze strukturální teorie grafů. Nejprve se zabýváme strukturou grafů které mají nikde nenulový 5-tok. Podáme charakteri- zaci takových grafů pomocí existence (1, 2)−faktorů. Ve druhé části zavedeme nový typ dekorace vrcholů grafu, kterému říkáme aditivní barvení. Aditivní barvení je injektivní barvení s omezeními danými grafem. Studujeme strukturu grafů které mají tuto dekoraci, a související algoritmické otázky. Ve třetí časti studujeme hypotézu kterou formuloval před asi dvaceti lety R. Stanley: je pravda, že U-polynom rozlišuje neizomorfní stromy? Dokážeme tuto hypotézu pro stromy- housenky bez vrcholů stupně dva. O tento výsledek se v minulých letech snažila řada vědců, například S. Noble. Ve čtvrté části studujeme strukturu nekonečných grafů které mají uplný graf jako minor nebo topologický minor. Klíčová slova: graf, nikde nenulový tok, faktor grafu, barvení grafů, izomorfismus grafů, strom, U-polynom, minor, topologický minor.
|
host ::
RSS.