Igor E. Zverovich
Basic perfect graphs and their extensions
Zverovich, Igor E.; Zverovich, Vadim
Abstract
In this article, we present a characterization of basic graphs in terms of forbidden induced subgraphs. This class of graphs was introduced by Conforti et al. (Square-free perfect graphs, J. Combin. Theory Ser. B, 90 (2) (2004) 257-307), and it plays an essential role in the announced proof of the Strong Perfect Graph Conjecture by Chudnovsky et al. (http://arxiv.org/PS_cache/math/ pdf/0212/0212070.pdf). Let G and H be graphs. A substitution of H in G replacing a vertex v∈V(G) is the graph G(v→H) consisting of disjoint union of H and G-v with the additional edge-set {xy:x∈V(H),y∈NG(v)}. For a class of graphs P, its substitutional closure P* consists of all graphs that can be obtained from graphs of P by repeated substitutions. We apply the reducing pseudopath method (Discrete Appl. Math. 128 (2-3) (2003) 487-509) to characterize the substitutional closure of the class of basic graphs in terms of forbidden induced subgraphs. © 2005 Elsevier B.V. All rights reserved.
Citation
Zverovich, I. E., & Zverovich, V. (2005). Basic perfect graphs and their extensions. Discrete Mathematics, 293(1-3), 291-311. https://doi.org/10.1016/j.disc.2004.08.033
Journal Article Type | Conference Paper |
---|---|
Publication Date | Apr 6, 2005 |
Journal | Discrete Mathematics |
Print ISSN | 0012-365X |
Publisher | Elsevier |
Peer Reviewed | Not Peer Reviewed |
Volume | 293 |
Issue | 1-3 |
Pages | 291-311 |
DOI | https://doi.org/10.1016/j.disc.2004.08.033 |
Keywords | perfect graphs, basic graphs, line graphs, substitutional closure, forbidden induced subgraphs |
Public URL | https://uwe-repository.worktribe.com/output/1052179 |
Publisher URL | http://dx.doi.org/10.1016/j.disc.2004.08.033 |
You might also like
Methods of Graph Decompositions
(2022)
Book
Modern Applications of Graph Theory
(2021)
Book
The likelihood of Braess' paradox in traffic networks
(2018)
Book Chapter
Downloadable Citations
About UWE Bristol Research Repository
Administrator e-mail: repository@uwe.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search