2019-04-30
Sum-perfect graphs
Publication
Publication
Discrete Applied Mathematics , Volume 259 p. 232- 239
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, . (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.
Additional Metadata | |
---|---|
doi.org/10.1016/j.dam.2018.12.015 | |
Discrete Applied Mathematics | |
Litjens, B., Polak, S., & Sivaraman, V. (2019). Sum-perfect graphs. Discrete Applied Mathematics, 259, 232–239. doi:10.1016/j.dam.2018.12.015 |