Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences

Details Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences

2011-05-14

arxiv.org/abs/1105.2874v1

Computer Science

Discrete Mathematics

14 Pages, 1 figure

Scientific paper

Clique separator decomposition introduced by Tarjan and Whitesides is one of the most important graph decompositions. A graph is an {\em atom} if it has no clique separator. A {\em hole} is a chordless cycle with at least five vertices, and an {\em antihole} is the complement graph of a hole. A graph is {\em weakly chordal} if it is hole- and antihole-free. $K_4-e$ is also called {\em diamond}. {\em Paraglider} has five vertices four of which induce a diamond, and the fifth vertex sees exactly the two vertices of degree two in the diamond. In this paper we show that atoms of hole- and diamond-free graphs (of hole- and paraglider-free graphs, respectively) are either weakly chordal or of a very specific structure. Hole- and paraglider-free graphs are perfect graphs. The structure of their atoms leads to efficient algorithms for various problems.

Affiliated with

Also associated with

No associations

Rating

Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Clique Separator Decomposition of Hole- and Diamond-Free Graphs and Algorithmic Consequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-579250