Generalised Dualities and Finite Maximal Antichains

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00206148" target="_blank" >RIV/00216208:11320/06:00206148 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Generalised Dualities and Finite Maximal Antichains

Original language description

We fully characterise the situations where the existence of a homomorphism from a digraph G to at least one of a finite set H of directed graphs is determined by a finite number of forbidden subgraphs. We prove that these situations, called generalised dualities, are characterised by the non-existence of a homomorphism to G from a finite set of forests. Furthermore, we characterise all finite maximal antichains in the partial order of directed graphs ordered by the existence of homomorphism. We show that these antichains correspond exactly to the generalised dualities. This solves a problem posed in [1]. Finally, we show that it is NP-hard to decide whether a finite set of digraphs forms a maximal antichain.

Czech name

—

Czech description

—

Type

D - Article in proceedings

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

2006

Confidentiality

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

Article name in the collection

Graph-Theoretic Concepts in Computer Science

ISBN

3-540-48381-0

ISSN

—

e-ISSN

—

Number of pages

10

Pages from-to

—

Publisher name

Springer

Place of publication

Berlin

Event location

Berlin

Event date

Jan 1, 2006

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000243130300003