1. Block-graph width
- Author
-
Chang, Maw-Shang, Hung, Ling-Ju, Kloks, Ton, and Peng, Sheng-Lung
- Subjects
- *
GRAPH theory , *WIDTH measurement , *ALGORITHMS , *PARAMETER estimation , *COMPLETE graphs , *SET theory - Abstract
Abstract: Let be a class of graphs. A graph has -width if there are independent sets in such that can be embedded into a graph such that for every edge in which is not an edge in , there exists an such that both endvertices of are in . For the class of block graphs we show that graphs with -width at most 4 are perfect. We also show that -width is NP-complete and show that it is fixed-parameter tractable. For the class of complete graphs, similar results are also obtained. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF