Reduced clique graphs of chordal graphs
Habib, Michel and Stacho, Juraj. (2012) Reduced clique graphs of chordal graphs. European Journal of Combinatorics, Vol.33 (No.5). pp. 712-735. ISSN 0195-6698Full text not available from this repository.
Official URL: http://dx.doi.org/10.1016/j.ejc.2011.09.031
We investigate the properties of chordal graphs that follow from the well-known fact that chordal graphs admit tree representations. In particular, we study the structure of reduced clique graphs which are graphs that canonically capture all tree representations of chordal graphs. We propose a novel decomposition of reduced clique graphs based on two operations: edge contraction and removal of the edges of a split. Based on this decomposition, we characterize asteroidal sets in chordal graphs, and discuss chordal graphs that admit a tree representation with a small number of leaves. © 2011 Elsevier Ltd.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics|
|Divisions:||Faculty of Science > Mathematics|
|Journal or Publication Title:||European Journal of Combinatorics|
|Page Range:||pp. 712-735|
|Access rights to Published version:||Restricted or Subscription Access|
Actions (login required)