BROWSE

Related Scientist

's photo.

수리 및 계산 과학 연구단
more info

ITEM VIEW & DOWNLOAD

Well-partitioned chordal graphs

Cited 0 time in webofscience Cited 0 time in scopus
104 Viewed 0 Downloaded
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).
URI
https://pr.ibs.re.kr/handle/8788114/12366
DOI
10.1016/j.disc.2022.112985
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.

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse