Well-partitioned chordal graphs

- Title
- Well-partitioned chordal graphs

- Author(s)
- Jungho Ahn; Jaffke, Lars; O-joung Kwon; Lima, Paloma T.

- Publication Date
- 2022-10

- Journal
- Discrete Mathematics, v.345, no.10

- Publisher
- Elsevier B.V.

- 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).

- ISSN
- 0012-365X

- Appears in Collections:
- Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > 1. Journal Papers (저널논문)

- Files in This Item:
- There are no files associated with this item.