New examples of minimal non-strongly-perfect graphs

Maria Chudnovsky; Cemil Dibek; Paul Seymour

doi:10.1016/j.disc.2021.112334

New examples of minimal non-strongly-perfect graphs

Maria Chudnovsky, Cemil Dibek, Paul Seymour

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

Abstract

A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.

Original language	American English
Article number	112334
Journal	Discrete Mathematics
Volume	344
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2021.112334
State	Published - May 2021

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Keywords

Forbidden induced subgraph characterization
New minimal examples
Strongly perfect graphs

Access to Document

10.1016/j.disc.2021.112334

Cite this

@article{b917c81f730846d4bcff37caafd9b037,

title = "New examples of minimal non-strongly-perfect graphs",

abstract = "A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.",

keywords = "Forbidden induced subgraph characterization, New minimal examples, Strongly perfect graphs",

author = "Maria Chudnovsky and Cemil Dibek and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2021",

month = may,

doi = "10.1016/j.disc.2021.112334",

language = "American English",

volume = "344",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - New examples of minimal non-strongly-perfect graphs

AU - Chudnovsky, Maria

AU - Dibek, Cemil

AU - Seymour, Paul

PY - 2021/5

Y1 - 2021/5

N2 - A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.

AB - A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.

KW - Forbidden induced subgraph characterization

KW - New minimal examples

KW - Strongly perfect graphs

UR - http://www.scopus.com/inward/record.url?scp=85100899236&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100899236&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2021.112334

DO - 10.1016/j.disc.2021.112334

M3 - Article

SN - 0012-365X

VL - 344

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 5

M1 - 112334

ER -

New examples of minimal non-strongly-perfect graphs

Abstract

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this