Narrow Results

We prove algorithmic characterizations of weakly chordal graphs, which lead to efficient parallel algorithms for recognizing P₅-free and -free weakly chordal graphs. For an input graph on n vertices and m edges, our algorithms run in O(log²n) time and require O(m²/log n) processors on the EREW PRAM model of computation. The proposed recognition algorithms efficiently detect P₅s and in weakly chordal graphs in O(log n) time with O(m²/logn) processors on the EREW PRAM. Additionally, we show how the algorithms can be augmented to provide a certificate for the existence of a P₅ (or a ) in case the input graph is not P₅-free (respectively, -free) weakly chordal.

Although the notion of a two-pair (a pair of vertices between which all induced paths have length 2) was invented for the class of weakly chordal graphs, two-pairs can also play a fundamental role for smaller graph classes. Indeed, two-pairs and chords of cycles can collaborate symmetrically to give parallel characterizations of weakly chordal, chordal, and strongly chordal graphs (and of distance-hereditary graphs).

A $k$ vertex coloring of a graph $G=(V,E)$ partitions the vertex set into $k$ color classes (or independent sets). In minimum vertex coloring problem, the aim is to minimize the number of colors used in a given graph. Here, we consider three variations of vertex coloring problem in which (i) each vertex in $G$ dominates a color class, (ii) each color class is dominated by a vertex and (iii) each vertex is dominating a color class and each color class is dominated by a vertex. These minimization problems are known as Min-Dominator-Coloring, Min-CD-Coloring and Min-Domination-Coloring, respectively. In this paper, we present approximation hardness results for these problems for some restricted class of graphs.