Forbidden induced pairs for perfectness and -colourability of graphs

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Ramsey's theorem strong perfect graph theorem

Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Abstract: 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

o m e g a

-colourable (that is, their chromatic number is equal to their clique number). More generally, we show characterizations of pairs

X, Y

for perfectness and

o m e g a

-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

o m e g a

-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

c h i

-boundedness and deciding

k

-colourability in polynomial time.

Review text

Summary: 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 \textit{C. Brause} et al. [Discrete Math. 342, No. 6, 1602--1608 (2019; Zbl 1414.05127); Discrete Appl. Math. 253, 14--24 (2019; Zbl 1401.05105)] 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 \(\chi\)-boundedness and deciding \(k\)-colourability in polynomial time.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138579)