Holes and a chordal cut in a graph

Abstract: A set

X

of vertices of a graph

G

is called a {em clique cut} of

G

if the subgraph of

G

induced by

X

is a complete graph and the number of connected components of

G - X

is greater than that of

G

. A clique cut

X

of

G

is called a {em chordal cut} of

G

if there exists a union

U

of connected components of

G - X

such that

G [U c u p X]

is a chordal graph. In this paper, we consider the following problem: Given a graph

G

, does the graph have a chordal cut? We show that

K_{2, 2, 2}

-free hole-edge-disjoint graphs have chordal cuts if they satisfy a certain condition.

This page was built for publication: Holes and a chordal cut in a graph