A generalization of chordal graphs

Abstract

This thesis introduces graph class C, a recognition algorithm for graphs in the class, and shows that some problems are NP-complete on the class. Class C is a generalization of chordal graphs. Informally, a graph is in class C if successively removing the neighborhoods of its simplicial vertices produces a null graph. More precisely, a graph G is in class C if G is the null graph or G contains a simplicial vertex v such that G - N[v] is in C. A greedy algorithm can recognize whether a graph is in class C in O(nm) time. The maximum independent set problem and the clique cover problem on class C can be solved in linear time using greeedy algorithms. However, the maximum clique problem and the coloring problem are NP-complete on the class.

This work also examines class K, the class of graphs in class C whose complements are also in class C, and shows that the maximum weighted independent set problem is NP-complete on the class. Class K generalizes split graphs, the class of graphs that are chordal and co-chordal. The four problems mentioned in relation to class C can be solved in linear time on class K using greedy algorithms. The same is known to be true for split graphs. However, while the maximum weighted independent set problem can be solved in polynomial time on split graphs, this problem is NP-complete on class K.