Finite dualities and map-critical graphs on a fixed surface

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Finite dualities and map-critical graphs on a fixed surface
Original language description
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
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

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

Similar results(10)