Holes and a chordal cut in a graph

Original · EN

A set X of vertices of a graph G is called a 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 chordal cut of G if there exists a union U of connected components of G-X such that G[U ∪ 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₂,₂,₂-free hole-edge-disjoint graphs have chordal cuts if they satisfy a certain condition.