Sum-perfect graphs

Bart Litjens; Sven C. Polak; Vaidy Sivaraman

doi:10.1016/j.dam.2018.12.015

Sum-perfect graphs

Bart Litjens
, Sven C. Polak
, Vaidy Sivaraman

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

115 Downloads (Pure)

Abstract

Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph
G to be sum-perfect if for every induced subgraph H of G, α(H) + ω(H) ≥ |V(H)|. (Here α
and ω denote the stability number and clique number, respectively.) We give a set of 27
graphs and we prove that a graph G is sum-perfect if and only if G does not contain any of
the graphs in the set as an induced subgraph.

Original language	Undefined/Unknown
Pages (from-to)	232-239
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	259
DOIs	https://doi.org/10.1016/j.dam.2018.12.015
Publication status	Published - 2019
Externally published	Yes

Access to Document

10.1016/j.dam.2018.12.015

1-s2.0-S0166218X18306589-mainFinal published version, 385 KBLicence: Taverne

https://dblp.org/db/journals/dam/dam259.html#LitjensPS19

Cite this

@article{b09d9a2212cb41c6b32b8c542421ca55,

title = "Sum-perfect graphs",

abstract = "Inspired by a famous characterization of perfect graphs due to Lov{\'a}sz, we define a graph G to be sum-perfect if for every induced subgraph H of G, α(H) + ω(H) ≥ |V(H)|. (Here α and ω denote the stability number and clique number, respectively.) We give a set of 27 graphs and we prove that a graph G is sum-perfect if and only if G does not contain any of the graphs in the set as an induced subgraph.",

author = "Bart Litjens and Polak, \{Sven C.\} and Vaidy Sivaraman",

note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",

year = "2019",

doi = "10.1016/j.dam.2018.12.015",

language = "Undefined/Unknown",

volume = "259",

pages = "232--239",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Sum-perfect graphs

AU - Litjens, Bart

AU - Polak, Sven C.

AU - Sivaraman, Vaidy

N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

PY - 2019

Y1 - 2019

N2 - Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph G to be sum-perfect if for every induced subgraph H of G, α(H) + ω(H) ≥ |V(H)|. (Here α and ω denote the stability number and clique number, respectively.) We give a set of 27 graphs and we prove that a graph G is sum-perfect if and only if G does not contain any of the graphs in the set as an induced subgraph.

AB - Inspired by a famous characterization of perfect graphs due to Lovász, we define a graph G to be sum-perfect if for every induced subgraph H of G, α(H) + ω(H) ≥ |V(H)|. (Here α and ω denote the stability number and clique number, respectively.) We give a set of 27 graphs and we prove that a graph G is sum-perfect if and only if G does not contain any of the graphs in the set as an induced subgraph.

U2 - 10.1016/j.dam.2018.12.015

DO - 10.1016/j.dam.2018.12.015

M3 - Article

SN - 0166-218X

VL - 259

SP - 232

EP - 239

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -