On graphs associated to posets, especially on cover-incomparability graphs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60461373%3A22340%2F13%3A43896409" target="_blank" >RIV/60461373:22340/13:43896409 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On graphs associated to posets, especially on cover-incomparability graphs
Original language description
We deal with posets and graphs associated to them. There are several standard ways how to associate a graph to a poset. Depending on the edge-set we may obtain comparability graphs, incomparability graphs or cover graphs. We study a new notion of cover-incomparabilty graphs (defined 2008). We first list several important properties of C-I graphs and then concentrate on complexity problems concerning C-I graphs. We prove that the recognizing C-I graphs is NP-complete for generel graphs while it is polynomial for the following subclasses of chordal graphs: Ptolemaic graphs, distance-hereditary graphs, and k-trees.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
—
Continuities
V - Vyzkumna aktivita podporovana z jinych verejnych zdroju
Others
Publication year
2013
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
Article name in the collection
Matematika na vysokých školách
ISBN
978-80-01-05325-6
ISSN
—
e-ISSN
—
Number of pages
3
Pages from-to
92-94
Publisher name
ČVUT
Place of publication
Praha
Event location
Herbertov
Event date
Sep 9, 2013
Type of event by nationality
CST - Celostátní akce
UT code for WoS article
—