Which k-trees are cover-incomparability graphs?

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60461373%3A22340%2F14%3A43895350" target="_blank" >RIV/60461373:22340/14:43895350 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S0166218X13005659" target="_blank" >http://www.sciencedirect.com/science/article/pii/S0166218X13005659</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Which k-trees are cover-incomparability graphs?

Popis výsledku v původním jazyce

In this paper we dea lwith cover?incomparability graphs o fposets.It is known that the class of cover?incomparability graphs is not closed on induced subgraphs which makes the study of structural properties of these graphs difficult. In this paper we introduce the notion of s-subgraph which enables us to define forbidden s-subgraphs (i.e. graphs that cannot appear as s-subgraphs of any cover?incomparability graph). We show that the family of minimal forbidden s-subgraphs is infinite even for cover?incomparability unit-interval graphs.Using the notion of s-subgraph we also answer the question which k-trees are cover?incomparability graphs and which chordal graphs without K4 are cover?incomparabilitygraphs.

Název v anglickém jazyce

Which k-trees are cover-incomparability graphs?

Popis výsledku anglicky

In this paper we dea lwith cover?incomparability graphs o fposets.It is known that the class of cover?incomparability graphs is not closed on induced subgraphs which makes the study of structural properties of these graphs difficult. In this paper we introduce the notion of s-subgraph which enables us to define forbidden s-subgraphs (i.e. graphs that cannot appear as s-subgraphs of any cover?incomparability graph). We show that the family of minimal forbidden s-subgraphs is infinite even for cover?incomparability unit-interval graphs.Using the notion of s-subgraph we also answer the question which k-trees are cover?incomparability graphs and which chordal graphs without K4 are cover?incomparabilitygraphs.

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í

2014

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.167

Číslo periodika v rámci svazku

20. April 2014

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

6

Strana od-do

222-227

Kód UT WoS článku

000333492800022

EID výsledku v databázi Scopus

—