Finite duality for some minor closed classes
Result 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.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
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.
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Electronic Notes in Discrete Mathematics
ISSN
1571-0653
e-ISSN
—
Volume of the periodical
29
Issue of the periodical within the volume
neuvedeno
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
7
Pages from-to
579-585
UT code for WoS article
—
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
BA - General mathematics
Year of implementation
2007