Forbidden induced pairs for perfectness and ω-colourability of graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F22%3A43965408" target="_blank" >RIV/49777513:23520/22:43965408 - 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 ω-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 C5) are perfect. Similarly, we characterise pairs {X, Y} such that all {X, Y}-free graphs (distinct from C5) are ω-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs {X, Y} for perfectness and ω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 n0, and similar characterisations subject to each subset of these additional constraints. (The classes are non-hereditary and the characterisations for perfectness and ω-colourability are different.) We build on recent results of Brause et al. on {K(1,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 χ-boundedness and deciding k-colourability in polynomial time.

Název v anglickém jazyce

Forbidden induced pairs for perfectness and ω-colourability of graphs

Popis výsledku anglicky

We characterise the pairs of graphs {X, Y} such that all {X, Y}-free graphs(distinct from C5) are perfect. Similarly, we characterise pairs {X, Y} such that all {X, Y}-free graphs (distinct from C5) are ω-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs {X, Y} for perfectness and ω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 n0, and similar characterisations subject to each subset of these additional constraints. (The classes are non-hereditary and the characterisations for perfectness and ω-colourability are different.) We build on recent results of Brause et al. on {K(1,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 χ-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

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

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

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

1077-8926

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

nestrankovano

Kód UT WoS článku

000797338500001

EID výsledku v databázi Scopus

2-s2.0-85129466862