Sum-perfect graphs
| Autor: | Bart Litjens, Vaidy Sivaraman, Sven Polak |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Applied Mathematics
010102 general mathematics Induced subgraph 0102 computer and information sciences 16. Peace & justice 01 natural sciences Graph Combinatorics 05C17 05C69 05C75 010201 computation theory & mathematics Computer Science::Discrete Mathematics FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics Combinatorics (math.CO) 0101 mathematics Clique number Mathematics |
| Zdroj: | Discrete Applied Mathematics, 259, 232-239 |
| ISSN: | 0166-218X |
| DOI: | 10.48550/arxiv.1710.07546 |
| Popis: | 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$, $\alpha(H) + \omega(H) \geq |V(H)|$. (Here $\alpha$ and $\omega$ 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. Comment: 10 pages, 3 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect