On graphs associated to posets, especially on cover-incomparability graphs

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On graphs associated to posets, especially on cover-incomparability graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On graphs associated to posets, especially on cover-incomparability graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

V - Vyzkumna aktivita podporovana z jinych verejnych zdroju

Rok uplatnění

2013

Kód důvěrnosti údajů

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

Název statě ve sborníku

Matematika na vysokých školách

ISBN

978-80-01-05325-6

ISSN

—

e-ISSN

—

Počet stran výsledku

3

Strana od-do

92-94

Název nakladatele

ČVUT

Místo vydání

Praha

Místo konání akce

Herbertov

Datum konání akce

9. 9. 2013

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—