Search

A graph is quasi-triangulated if each of its induced subgraphs has a vertex that is either simplicial (its neighbours form a clique) or co-simplicial (its non-neighbours form an independent set) in the induced subgraph. The problem of characterizing quasi-triangulated graphs by minimal forbidden induced subgraphs is open. We show that a graph is quasi-triangulated if it does not contain as induced subgraph any of the graphs C 5 , P 5 , P 3 + P 3 , fence , or their complements. The fence is obtained from a P 4 by substituting two adjacent vertices for each end-vertex of the P 4 and two non-adjacent vertices for each interior vertex of the P 4. We also provide an efficient algorithm to recognize the subclass Q T k , for fixed k ≥ 0 , of quasi-triangulated graphs studied in the literature. [ABSTRACT FROM AUTHOR]

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156-2162, ). We show that whether a building-free graph contains a sun can be decided in O(min{ mn, m n}) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs. [ABSTRACT FROM AUTHOR]

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is a k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos [2002], motivated by the search for underlying phylogenetic trees. Their results imply an O(n³)-time recognition algorithm for 4-leaf powers. Recently, Rautenbach [2006] as well as Dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. We give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. As a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers. [ABSTRACT FROM AUTHOR]

Abstract: Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449–473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete. [Copyright &y& Elsevier]

The κ-partition problem is as follows: Given a graph G and a positive integer κ, partition the vertices of G into at most κ parts A1, A2,...,Aκ, where it may be specified that Ai induces a stable set, a clique, or an arbitrary subgraph, and pairs Ai, Aj (i ≠ j) be completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list κ-partition problem generalizes the κ-partition problem by specifying for each vertex x, a list L(x) of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list κ-partition problems: e.g., 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2- clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete. [ABSTRACT FROM AUTHOR]

The class of hhds-free graphs properly generalizes the classes of strongly chordal graphs and distance-hereditary graphs, and forms a restriction of the class of perfectly orderable graphs. The problem of recognizing hhds-free graphs in polynomial time was posed by Brandstädt (Problem session, Dagstuhl seminor No. 04221, 2004), and Nikolopoulos and Palios (Proceedings of the 31st International Workshop on Graph Theoretic Concepts in Computer Science, 2005) gave an O( m n 2) algorithm. We present an O( n 3)-time algorithm for the problem. Our algorithm demonstrates a relationship between hhds-free graphs and strongly chordal graphs similar to that which is known to exist between hhd-free graphs and chordal graphs. [ABSTRACT FROM AUTHOR]

We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O(mn²) to O(m²) and the space complexity from O(n³) to O(m+n), and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from O(mn²) to O(n³) and the complexity of the independent set and clique cover problems is improved from O(n4) to O(mn). The space complexity of our optimization algorithms is O(m + n). [ABSTRACT FROM AUTHOR]

The class of weakly triangulated comparability graphs and their complements are generalizations of interval graphs and chordal comparability graphs. We show that problems on these classes of graphs can be solved efficiently by transforming them into problems on chordal bipartite graphs. We show that recognition and independent set on weakly triangulated comparability graphs can be solved in O(n²) time in this manner, and that the number of weakly triangulated comparability graphs is 2#Θ(nlog²n)$. We also give algorithms to compute transitive closure and transitive reduction in O(n²loglogn) time if the underlying undirected graph of the transitive closure is a weakly triangulated comparability graph. [ABSTRACT FROM AUTHOR]

We present an-time algorithm for computing a maximum cardinality induced matching and a minimum cardinality cover by chain subgraphs for convex bipartite graphs. This improves the previous time bound of . [Copyright &y& Elsevier]

Abstract: Many recognition problems for special classes of graphs and cycles can be reduced to finding and listing induced paths and cycles in a graph. We design algorithms to list all ’s in time, and for all ’s in time, where , respectively, , are the number of ’s, respectively, ’s, of a graph . We also provide an algorithm to find a , , in time if is odd, and if is even. As applications of our findings, we give algorithms to recognize quasi-triangulated graphs and brittle graphs. Our algorithms’ time bounds are incomparable with previously known algorithms. [Copyright &y& Elsevier]

Golumbic, Kaplan, and Shamir, in their paper [M.C. Golumbic, H. Kaplan, R. Shamir, Graph sandwich problems, J. Algorithms 19 (1995) 449–473] on graph sandwich problems published in 1995, left the status of sandwich problems for strongly chordal graphs and chordal bipartite graphs open. We prove that the sandwich problem for strongly chordal graphs is NP-complete. We also give some comments on the computational complexity of the sandwich problem for chordal bipartite graphs. [Copyright &y& Elsevier]

This paper presents new algorithms for recognizing several classes of perfectly orderable graphs. Bipolarizable and P4-simplicial graphs are recognized in O(n3.376) time, improving the previous bounds of O(n4) and O(n5), respectively. Brittle and semi-simplicial graphs are recognized in O(n3) time using a randomized algorithm, and O(n3 log2n) time if a deterministic algorithm is required. The best previous time bound for recognizing these classes of graphs is O(m2). Welsh–Powell opposition graphs are recognized in O(n3) time, improving the previous bound of O(n4). HHP-free graphs and maxibrittle graphs are recognized in O(mn) and O(n3.376) time, respectively. [Copyright &y& Elsevier]