Finite dualities and map-critical graphs on a fixed surface

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10104488" target="_blank" >RIV/00216208:11320/12:10104488 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.jctb.2011.06.001" target="_blank" >http://dx.doi.org/10.1016/j.jctb.2011.06.001</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.jctb.2011.06.001" target="_blank" >10.1016/j.jctb.2011.06.001</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Finite dualities and map-critical graphs on a fixed surface

Popis výsledku v původním jazyce

Let K be a class of graphs. A pair (F, U) is a finite duality in K if U is an element of K, F is a finite set of graphs, and for any graph G in L we have G {= U if and only if F not equal to or less than G for all F is an element of F where "{=" is the homomorphism order. We also say U is a dual graph in k. We prove that the class of planar graphs has no finite dualities except for two trivial cases. We also prove that the class of toroidal graphs has no 5-colorable dual graphs except for two trivial cases. In a sharp contrast, for a higher genus orientable surface S we show that Thomassen''s result (Thomassen, 1997 [17]) implies that the class, G(S), of all graphs embeddable in S has a number of finite dualities. Equivalently, our first result shows that for every planar core graph H except K(1) and K(4), there are infinitely many minimal planar obstructions for H-coloring (Hell and Nesetril, 1990 [4]), whereas our later result gives a converse of Thomassen''s theorem (Thomassen, 1997

Název v anglickém jazyce

Finite dualities and map-critical graphs on a fixed surface

Popis výsledku anglicky

Let K be a class of graphs. A pair (F, U) is a finite duality in K if U is an element of K, F is a finite set of graphs, and for any graph G in L we have G {= U if and only if F not equal to or less than G for all F is an element of F where "{=" is the homomorphism order. We also say U is a dual graph in k. We prove that the class of planar graphs has no finite dualities except for two trivial cases. We also prove that the class of toroidal graphs has no 5-colorable dual graphs except for two trivial cases. In a sharp contrast, for a higher genus orientable surface S we show that Thomassen''s result (Thomassen, 1997 [17]) implies that the class, G(S), of all graphs embeddable in S has a number of finite dualities. Equivalently, our first result shows that for every planar core graph H except K(1) and K(4), there are infinitely many minimal planar obstructions for H-coloring (Hell and Nesetril, 1990 [4]), whereas our later result gives a converse of Thomassen''s theorem (Thomassen, 1997

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Combinatorial Theory. Series B

ISSN

0095-8956

e-ISSN

—

Svazek periodika

102

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

131-152

Kód UT WoS článku

000297448800011

EID výsledku v databázi Scopus

—