The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

Introducing subclasses of basic chordal graphs

Basic chordal graphs arose when comparing clique trees of chordal graphs and compatible trees of dually chordal graphs. They were defined as those chordal graphs whose clique trees are exactly the compatible trees of its clique graph.In this work, we consider some subclasses of basic chordal graphs, like hereditary basic chordal graphs, basic DV and basic RDV graphs, we characterize them and we find some other properties they have, mostly involving clique graphs.     

On 2-walks in chordal planar graphs

A 2-walk is a closed spanning trail which uses every vertex at most twice. A graph is said to be chordal if each cycle different from a 3-cycle has a chord. We prove that every chordal planar graph G with toughness has a 2-walk.     

Polarity of chordal graphs

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs; nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus on a special case of polarity (called monopolarity) which turns out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions; it turns out that they can all be described by a certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm.     

Cover-Incomparability Graphs of Posets

Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems are also stated.     

Geodeticity of the contour of chordal graphs

A vertex v is a boundary vertex of a connected graph G if there exists a vertex u such that no neighbor of v is further away from u than v. Moreover, if no vertex in the whole graph V(G) is further away from u than v, then v is called an eccentric vertex of G. A vertex v belongs to the contour of G if no neighbor of v has an eccentricity greater than the eccentricity of v. Furthermore, if no vertex in the whole graph V(G) has an eccentricity greater than the eccentricity of v, then v is called a peripheral vertex of G. This paper is devoted to study these kinds of vertices for the family of chordal graphs. Our main contributions are, firstly, obtaining a realization theorem involving the cardinalities of the periphery, the contour, the eccentric subgraph and the boundary, and secondly, proving both that the contour of every chordal graph is geodetic and that this statement is not true for every perfect graph.     

An implicit representation of chordal comparability graphs in linear time

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n²).     

On the interval completion of chordal graphs

For a given graph G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F) of G is an interval graph and |F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.     

Brambles and independent packings in chordal graphs

An independent packing of triangles is a set of pairwise disjoint triangles, no two of which are joined by an edge. A triangle bramble is a set of triangles, every pair of which intersect or are joined by an edge. More generally, I consider independent packings and brambles of any specified connected graphs, not just triangles. I give a min-max theorem for the maximum number of graphs in an independent packing of any family of connected graphs in a chordal graph, and a dual min-max theorem for the maximum number of graphs in a bramble in a chordal graph.     

Chordal bipartite, strongly chordal, and strongly chordal bipartite graphs

Robert E. Jamison characterized chordal graphs by the edge set of every k-cycle being the symmetric difference of k−2 triangles. Strongly chordal (and chordal bipartite) graphs can be similarly characterized in terms of the distribution of triangles (respectively, quadrilaterals). These results motivate a definition of ‘strongly chordal bipartite graphs’, forming a class intermediate between bipartite interval graphs and chordal bipartite graphs.     

A linear time algorithm to list the minimal separators of chordal graphs

Kumar and Madhavan [Minimal vertex separators of chordal graphs, Discrete Appl. Math. 89 (1998) 155-168] gave a linear time algorithm to list all the minimal separators of a chordal graph. In this paper we give another linear time algorithm for the same purpose. While the algorithm of Kumar and Madhavan requires that a specific type of PEO, namely the MCS PEO is computed first, our algorithm works with any PEO. This is interesting when we consider the fact that there are other popular methods such as Lex BFS to compute a PEO for a given chordal graph.     

On the strong chromatic index and maximum induced matching of tree-cographs,permutation graphs and chordal bipartite graphs

We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the input. We also show that there exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs.     

Connected matchings in chordal bipartite graphs

A connected matching in a graph is a collection of edges that are pairwise disjoint but joined by another edge of the graph. Motivated by applications to Hadwiger’s conjecture, Plummer, Stiebitz, and Toft (2003) introduced connected matchings and proved that, given a positive integer $k$, determining whether a graph has a connected matching of size at least $k$ is NP-complete. Cameron (2003) proved that this problem remains NP-complete on bipartite graphs, but can be solved in polynomial-time on chordal graphs. We present a polynomial-time algorithm that finds a maximum connected matching in a chordal bipartite graph. This includes a novel edge-without-vertex-elimination ordering of independent interest. We give several applications of the algorithm, including computing the Hadwiger number of a chordal bipartite graph, solving the unit-time bipartite margin-shop scheduling problem in the case in which the bipartite complement of the precedence graph is chordal bipartite, and determining–in a totally balanced binary matrix–the largest size of a square sub-matrix that is permutation equivalent to a matrix with all zero entries above the main diagonal.     

Two methods for the generation of chordal graphs

In this paper two methods for automatic generation of connected chordal graphs are proposed: the first one is based on new results concerning the dynamic maintenance of chordality under edge insertions; the second is based on expansion/merging of maximal cliques. Theoretical and experimental results are presented. In both methods, chordality is preserved along the whole generation process. L. Markenzon’s research is partially supported by grant 301068/2003-8, CNPq, Brazil.     

Long paths and toughness of k-trees and chordal planar graphs

We show that every $k$-tree of toughness greater than $\frac{k}{3}$ is Hamilton-connected for $k\ge 3$. (In particular, chordal planar graphs of toughness greater than 1 are Hamilton-connected.) This improves the result of Broersma et al. (2007) and generalizes the result of Böhme et al. (1999).On the other hand, we present graphs whose longest paths are short. Namely, we construct 1-tough chordal planar graphs and 1-tough planar 3-trees, and we show that the shortness exponent of the class is 0, at most ${log}_{30}22$, respectively. Both improve the bound of Böhme et al. Furthermore, the construction provides $k$-trees (for $k\ge 4$) of toughness greater than 1.     

Strictly chordal graphs are leaf powers

A fundamental problem in computational biology is the phylogeny reconstruction for a set of specific organisms. One of the graph theoretical approaches is to construct a similarity graph on the set of organisms where adjacency indicates evolutionary closeness, and then to reconstruct a phylogeny by computing a tree interconnecting the organisms such that leaves in the tree are labeled by the organisms and every organism appears as a leaf in the tree. The similarity graph is simple and undirected. For any pair of adjacent organisms in the similarity graph, their distance in the output tree, which is measured by the number of edges on the path connecting them, must be less than some pre-specified bound. This is known as the problem of recognizing leaf powers and computing leaf roots. Graphs that are leaf powers are known to be chordal. It is shown in this paper that all strictly chordal graphs are leaf powers and a linear time algorithm is presented to compute a leaf root for any given strictly chordal graph. An intermediate root-and-power problem, the Steiner root problem, is also examined.     

Characterization of digraphs with equal domination graphs and underlying graphs

A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)] whenever (u,z)∈A(D) or (v,z)∈A(D) for every other vertex z∈V(D). The underlying graph of a digraph D, UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.