Well-partitioned chordal graphs

Abstract

We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call well-partitioned chordal graphs. A connected graph G is a well-partitioned chordal graph if there exist a partition P of the vertex set of G into cliques and a tree T having P as a vertex set such that for distinct X,Y∈P, (1) the edges between X and Y in G form a complete bipartite subgraph whose parts are some subsets of X and Y, if X and Y are adjacent in T, and (2) there are no edges between X and Y in G otherwise. A split graph with vertex partition (C,I) where C is a clique and I is an independent set is a well-partitioned chordal graph as witnessed by a star T having C as the center and each vertex in I as a leaf, viewed as a clique of size 1. We characterize well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given a graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal.

We observe that there are problems, for instance Densest k-Subgraph and b-Coloring, that are polynomial-time solvable on split graphs but become NP -hard on well-partitioned chordal graphs. On the other hand, we show that the Geodetic Set problem, known to be NP -hard on chordal graphs, can be solved in polynomial time on well-partitioned chordal graphs.

We also answer two combinatorial questions on well-partitioned chordal graphs that are open on chordal graphs, namely that each well-partitioned chordal graph admits a polynomial-time constructible tree 3-spanner, and that each (2-connected) well-partitioned chordal graph has a vertex that intersects all its longest paths (cycles).