Název:	Forbidden induced pairs for perfectness and ω-colourability of graphs
Autoři:	Chudnovsky, Maria Kabela, Adam Li, Binlong Vrána, Petr
Citace zdrojového dokumentu:	CHUDNOVSKY, M. KABELA, A. LI, B. VRÁNA, P. Forbidden induced pairs for perfectness and ω-colourability of graphs. Electronic Journal of Combinatorics, 2022, roč. 29, č. 2, s. nestránkováno. ISSN: 1097-1440
Datum vydání:	2022
Nakladatel:	Australian National University
Typ dokumentu:	postprint postprint
URI:	2-s2.0-85129466862 http://hdl.handle.net/11025/49631
ISSN:	1077-8926
Klíčová slova:	perfektní graf;vrcholové obarvení;zakázaný idukovaný podgraf
Klíčová slova v dalším jazyce:	perfect graphs;vertex colouring;forbidden induced subgraphs
Abstrakt v další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.
Práva:	© authors
Vyskytuje se v kolekcích:	Postprinty / Postprints (KMA) Postprinty / Postprints (NTIS) OBD

Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.