Forbidden induced pairs for perfectness and omega-colourability of graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F22%3A00128976" target="_blank" >RIV/00216224:14330/22:00128976 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.37236/10708" target="_blank" >https://doi.org/10.37236/10708</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37236/10708" target="_blank" >10.37236/10708</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Forbidden induced pairs for perfectness and omega-colourability of graphs

Popis výsledku v původním jazyce

We characterise the pairs of graphs {X, Y} such that all {X, Y}-free graphs (distinct from C-5) are perfect. Similarly, we characterise pairs {X, Y} such that all {X, Y}-free graphs (distinct from C-5) are omega-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs {X, Y} for perfectness and omega-colourability of all connected {X, Y}-free graphs which are of independence at least 3, distinct from an odd cycle, and of order at least n(0), and similar characterisations subject to each subset of these additional constraints. (The classes are non-hereditary and the characterisations for perfectness and omega-colourability are different.) We build on recent results of Brause et al. on {K-1,K-3, Y}-free graphs, and we use Ramsey's Theorem and the Strong Perfect Graph Theorem as main tools. We relate the present characterisations to known results on forbidden pairs for chi-boundedness and deciding k-colourability in polynomial time.

Název v anglickém jazyce

Forbidden induced pairs for perfectness and omega-colourability of graphs

Popis výsledku anglicky

We characterise the pairs of graphs {X, Y} such that all {X, Y}-free graphs (distinct from C-5) are perfect. Similarly, we characterise pairs {X, Y} such that all {X, Y}-free graphs (distinct from C-5) are omega-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs {X, Y} for perfectness and omega-colourability of all connected {X, Y}-free graphs which are of independence at least 3, distinct from an odd cycle, and of order at least n(0), and similar characterisations subject to each subset of these additional constraints. (The classes are non-hereditary and the characterisations for perfectness and omega-colourability are different.) We build on recent results of Brause et al. on {K-1,K-3, Y}-free graphs, and we use Ramsey's Theorem and the Strong Perfect Graph Theorem as main tools. We relate the present characterisations to known results on forbidden pairs for chi-boundedness and deciding k-colourability in polynomial time.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

29

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

33

Strana od-do

1-33

Kód UT WoS článku

000797338500001

EID výsledku v databázi Scopus

2-s2.0-85129466862