Which distance-hereditary graphs are cover?incomparability graphs?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60461373%3A22340%2F13%3A43895366" target="_blank" >RIV/60461373:22340/13:43895366 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.dam.2013.01.017" target="_blank" >http://dx.doi.org/10.1016/j.dam.2013.01.017</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.dam.2013.01.017" target="_blank" >10.1016/j.dam.2013.01.017</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Which distance-hereditary graphs are cover?incomparability graphs?

Popis výsledku v původním jazyce

In this paper we deal with cover?incomparability graphs of posets, or briefly C?I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C?I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C?I graphs? It follows that C?I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C?I graphs in general is known to be NP-complete

Název v anglickém jazyce

Which distance-hereditary graphs are cover?incomparability graphs?

Popis výsledku anglicky

In this paper we deal with cover?incomparability graphs of posets, or briefly C?I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C?I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C?I graphs? It follows that C?I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C?I graphs in general is known to be NP-complete

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

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 periodika

DISCRETE APPLIED MATHEMATICS

ISSN

0166-218X

e-ISSN

—

Svazek periodika

Vol.161

Číslo periodika v rámci svazku

Issues 13-14

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

6

Strana od-do

2095-2100

Kód UT WoS článku

000320680400030

EID výsledku v databázi Scopus

—