Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F22%3A43965406" target="_blank" >RIV/49777513:23520/22:43965406 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.disc.2022.112837" target="_blank" >https://doi.org/10.1016/j.disc.2022.112837</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4

Popis výsledku v původním jazyce

For every graph X, we consider the class of all connected {K(1,3), X}-free graphs which are distinct from an odd cycle and have independence number at least 4, and we show that all graphs in the class are perfect if and only if X is an induced subgraph of some of P6, K1 ∪ P5, 2P3, Z2 or K1 ∪ Z1. Furthermore, for X chosen as 2K1 ∪ K3, we list all eight imperfect graphs belonging to the class; and for every other choice of X, we show that there are infinitely many such graphs. In addition, for X chosen as B(1,2), we describe the structure of all imperfect graphs in the class.

Název v anglickém jazyce

Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4

Popis výsledku anglicky

For every graph X, we consider the class of all connected {K(1,3), X}-free graphs which are distinct from an odd cycle and have independence number at least 4, and we show that all graphs in the class are perfect if and only if X is an induced subgraph of some of P6, K1 ∪ P5, 2P3, Z2 or K1 ∪ Z1. Furthermore, for X chosen as 2K1 ∪ K3, we list all eight imperfect graphs belonging to the class; and for every other choice of X, we show that there are infinitely many such graphs. In addition, for X chosen as B(1,2), we describe the structure of all imperfect graphs in the class.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA20-09525S" target="_blank" >GA20-09525S: Strukturální vlastnosti tříd grafů charakterizovaných zakázanými podgrafy</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

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 MATHEMATICS

ISSN

0012-365X

e-ISSN

1872-681X

Svazek periodika

345

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

8

Strana od-do

nestrankovano

Kód UT WoS článku

000784329800017

EID výsledku v databázi Scopus

2-s2.0-85125796942