On powers and centers of chordal graphs

A graph is chordal if every cycle of length strictly greater than three has a chord. A necessary and sufficient condition is given for all powers of a chordal graph to be chordal. In addition, it is shown that for connected chordal graphs the center (the set of all vertices with minimum eccentricity) always induces a connected subgraph. A relationship between the radius and diameter of chordal graphs is also established.     

Restricted unimodular chordal graphs

A chordal graph is called restricted unimodular if each cycle of its vertex‐clique incidence bipartite graph has length divisible by 4. We characterize these graphs within all chordal graphs by forbidden induced subgraphs, by minimal relative separators, and in other ways. We show how to construct them by starting from block graphs and multiplying vertices subject to a certain restriction, which leads to a linear‐time recognition algorithm. We show how they are related to other classes such as distance‐hereditary chordal graphs and strongly chordal graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 121–136, 1999     

On the Structure of Bull-Free Perfect Graphs, 2: the Weakly Chordal Case

 A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. A graph is perfectly orderable if it admits an ordering such that the greedy sequential method applied on this ordering produces an optimal coloring for every induced subgraph. Chvátal conjectured that every bull-free graph with no odd hole or antihole is perfectly orderable. In a previous paper we studied the structure of general bull-free perfect graphs, and reduced Chvátal's conjecture to the case of weakly chordal graphs. Here we focus on weakly chordal graphs, and we reduce Chvátal's conjecture to a restricted case. Our method lays out the structure of all bull-free weakly chordal graphs. These results have been used recently by Hayward to establish Chvátal's conjecture for this restricted case and therefore in full. Received: November 26, 1997?Final version received: February 27, 2001     

Asteroids in rooted and directed path graphs

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a strong path. Two non-adjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree.     

A characterization of signed graphs with generalized perfect elimination orderings

An important property of chordal graphs is that these graphs are characterized by the existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal.     

Cohen-Macaulay chordal graphs

We classify all Cohen-Macaulay chordal graphs. In particular, it is shown that a chordal graph is Cohen-Macaulay if and only if it is unmixed.     

Characterizing directed path graphs by forbidden asteroids

An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it does not contain an asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a special connection. Two non‐adjacent vertices are linked by a special connection if either they have a common neighbor or they are the endpoints of two vertex‐disjoint chordless paths satisfying certain conditions. A special asteroidal triple is an asteroidal triple such that each pair is linked by a special connection. We prove that a chordal graph is a directed path graph if and only if it does not contain a special asteroidal triple. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:103‐112, 2011     

Algorithmic aspects of clique-transversal and clique-independent sets

A minimum clique-transversal set MCT(G) of a graph G=(V,E) is a set SV of minimum cardinality that meets all maximal cliques in G. A maximum clique-independent set MCI(G) of G is a set of maximum number of pairwise vertex-disjoint maximal cliques. We prove that the problem of finding an MCT(G) and an MCI(G) is NP-hard for cocomparability, planar, line and total graphs. As an interesting corollary we obtain that the problem of finding a minimum number of elements of a poset to meet all maximal antichains of the poset remains NP-hard even if the poset has height two, thereby generalizing a result of Duffas et al. (J. Combin. Theory Ser. A 58 (1991) 158–164). We present a polynomial algorithm for the above problems on Helly circular-arc graphs which is the first such algorithm for a class of graphs that is not clique-perfect. We also present polynomial algorithms for the weighted version of the clique-transversal problem on strongly chordal graphs, chordal graphs of bounded clique size, and cographs. The algorithms presented run in linear time for strongly chordal graphs and cographs. These mark the first attempts at the weighted version of the problem.     

弦图子类的全控制函数

本文首先证明了k-全控制问题和符号全控制问题在双弦图上均为NP-完全的.其次,在强消去序已给定的强弦图上,给出了求解符号全控制、负全控制、k-全控制和k-全控制问题的统一的O(m+n)时间算法.     

A Gröbner basis characterization for chordal comparability graphs

In this paper, we study toric ideals associated with multichains of posets. It is shown that the comparability graph of a poset is chordal if and only if there exists a quadratic Gröbner basis of the toric ideal of the poset. Strong perfect elimination orderings of strongly chordal graphs play an important role.     

Intersection models of weakly chordal graphs

We first present new structural properties of a two-pair in various graphs. A two-pair is used in a well-known characterization of weakly chordal graphs. Based on these properties, we prove the main theorem: a graph G is a weakly chordal ()-free graph if and only if G is an edge intersection graph of subtrees on a tree with maximum degree 4. This characterizes the so called [4, 4, 2] graphs. The proof of the theorem constructively finds the representation. Thus, we obtain an algorithm to construct an edge intersection model of subtrees on a tree with maximum degree 4 for such a given graph. This is a recognition algorithm for [4, 4, 2] graphs.     

Special Eccentric Vertices for the Class of Chordal Graphs and Related Classes

A vertex is simplicial if the vertices of its neighborhood are pairwise adjacent. It is known that, for every vertex v of a chordal graph, there exists a simplicial vertex among the vertices at maximum distance from v. Here we prove similar properties in other classes of graphs related to that of chordal graphs. Those properties will not be in terms of simplicial vertices, but in terms of other types of vertices that are used to characterize those classes.     

Strong clique trees,neighborhood trees,and strongly chordal graphs

Maximal complete subgraphs and clique trees are basic to both the theory and applications of chordal graphs. A simple notion of strong clique tree extends this structure to strongly chordal graphs. Replacing maximal complete subgraphs with open or closed vertex neighborhoods discloses new relationships between chordal and strongly chordal graphs and the previously studied families of chordal bipartite graphs, clique graphs of chordal graphs (dually chordal graphs), and incidence graphs of biacyclic hypergraphs. © 2000 John Wiley & Sons, Inc. J. Graph Theory 33: 151–160, 2000     

On the Structure of Contractible Vertex Pairs in Chordal Graphs

An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph.     

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.     

Bounding the Clique‐Width of H‐Free Chordal Graphs

A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P₄‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K₄‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs.     

Variations of maximum-clique transversal sets on graphs

A maximum-clique transversal set of a graph G is a subset of vertices intersecting all maximum cliques of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we introduce the concept of maximum-clique perfect and some variations of the maximum-clique transversal set problem such as the {k}-maximum-clique, k-fold maximum-clique, signed maximum-clique, and minus maximum-clique transversal problems. We show that balanced graphs, strongly chordal graphs, and distance-hereditary graphs are maximum-clique perfect. Besides, we present a unified approach to these four problems on strongly chordal graphs and give complexity results for the following classes of graphs: split graphs, balanced graphs, comparability graphs, distance-hereditary graphs, dually chordal graphs, doubly chordal graphs, chordal graphs, planar graphs, and triangle-free graphs.     

Several results on chordal bipartite graphs

The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is shown that, to any vertex of a chordal bipartite graph an edge may be added such that the chordality is maintained.     

On the tree representation of chordal graphs

We introduce the notion of the boundary clique and the k-overlap clique graph and prove the following: Every incomplete chordal graph has two nonadjacent simplicial vertices lying in boundary cliques. An incomplete chordal graph G is k-connected if and only if the k-overlap clique graph g_k(G) is connected. We give an algorithm to construct a clique tree of a connected chordal graph and characterize clique trees of connected chordal graphs using the algorithm.     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.