Full metadata record
DC poleHodnotaJazyk
dc.contributor.authorChudnovsky, Maria-
dc.contributor.authorKabela, Adam-
dc.contributor.authorLi, Binlong-
dc.contributor.authorVrána, Petr-
dc.date.accessioned2022-09-12T10:00:23Z-
dc.date.available2022-09-12T10:00:23Z-
dc.date.issued2022-
dc.identifier.citationCHUDNOVSKY, 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-1440cs
dc.identifier.issn1077-8926-
dc.identifier.uri2-s2.0-85129466862-
dc.identifier.urihttp://hdl.handle.net/11025/49631-
dc.format33 s.cs
dc.format.mimetypeapplication/pdf
dc.language.isoenen
dc.publisherAustralian National Universityen
dc.relation.ispartofseriesElectronic Journal of Combinatoricsen
dc.rights© authorsen
dc.subjectperfektní grafcs
dc.subjectvrcholové obarvenícs
dc.subjectzakázaný idukovaný podgrafcs
dc.titleForbidden induced pairs for perfectness and ω-colourability of graphsen
dc.typepostprintcs
dc.typepostprinten
dc.rights.accessopenAccessen
dc.type.versionacceptedVersionen
dc.description.abstract-translatedWe 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.en
dc.subject.translatedperfect graphsen
dc.subject.translatedvertex colouringen
dc.subject.translatedforbidden induced subgraphsen
dc.identifier.doi10.37236/10708-
dc.type.statusPeer-revieweden
dc.identifier.document-number797338500001-
dc.identifier.obd43936407-
dc.project.IDGA20-09525S/Strukturální vlastnosti tříd grafů charakterizovaných zakázanými indukovanými podgrafycs
dc.project.IDGA17-04611S/Ramseyovské aspekty barvení grafůcs
Vyskytuje se v kolekcích:Postprinty / Postprints (KMA)
Postprinty / Postprints (NTIS)
OBD

Soubory připojené k záznamu:
Soubor VelikostFormát 
2108.07071.pdf1,23 MBAdobe PDFZobrazit/otevřít
Zobrazit minimální záznam Zobrazit statistiky


Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam: http://hdl.handle.net/11025/49631

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

hledání
navigace
  1. DSpace at University of West Bohemia
  2. Publikační činnost / Publications
  3. OBD