Finite duality for some minor closed classes

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F07%3A00005050" target="_blank" >RIV/00216208:11320/07:00005050 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Finite duality for some minor closed classes
Original language description
Let K be a class of finite graphs and F1,...,Fm be a set of finite graphs. Then, K is said to have finite-duality if there exists a graph U in K such that for any graph G in K, G is homomorphic to U if and only if Fi is not homomorphic to G, for all i=1,2,,m. In this note, we answer this positively a problem of the first author by showing minor closed subclasses containing arbitrary long anti-chains and yet having the finite-duality property.
Czech name
Konečná dualita pro některé minorově uzavřené třídy
Czech description
Nechť K je třída konečných grafů a F1,..., Fm je množina konečných grafů. Potom řekneme, že K má konečnou dualitu, pokud existuje graf U takový, že pro každý graf G z K, G je homomorfní s U, právě když Fi není homomorfní s G, pro všechna i=1,...,m. V tomto článku pozitivně vyřešíme problém prvního autora, když zkonstruujeme minorově uzavřené třídy obsahující libovolně dlouhé antiřetězce a mající konečnou dualitu.

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
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)