Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

On retracts,absolute retracts,and foldings in cographs

A retract of a graph G is an induced subgraph H of G such that there exists a homomorphism \(\rho :G \rightarrow H\). When both G and H are cographs, we show that the problem to determine whether H is a retract of G is NP-complete; moreover, we show that this problem on cographs is fixed-parameter tractable when parameterized by the size of H. When restricted to the class of threshold graphs or to the class of trivially perfect graphs, the retract problem becomes tractable in polynomial time. The retract problem is also solvable in linear time when one cograph is given as an induced subgraph of the other. We characterize absolute retracts for the class of cographs. Foldings generalize retractions. We show that the problem to fold a trivially perfect graph onto a largest possible clique is NP-complete.     

Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

Hamiltonian Path/Cycle are well known NP-complete problems on general graphs, but their complexity status for permutation graphs has been an open question in algorithmic graph theory for many years. In this paper, we prove that theHamiltonian Path problem is solvable in polynomial time even for the larger class of cocomparability graphs. Our result is based on a nice relationship between Hamiltonian paths and the bump number of partial orders. As another consequence we get a new interpretation of the bump number in terms of path partitions, leading to polynomial time solutions of theHamiltonian Path/Cycle Completion problems in cocomparability graphs.This research was supported in part by ONR for third author and by NSERC under grant number A1798 for fourth author.     

Contractibility and NP-completeness

For a fixed graph H, let H-CON denote the problem of determining whether a given graph is contractible to H. The complexity of H-CON is studied for H belonging to certain classes of graphs, together covering all connected graphs of order at most 4. In particular, H-CON is NP-complete if H is a connected triangle-free graph other than a star. For each connected graph H of order at most 4 other than P₄ and C₄, H-CON is solvable in polynomial time.     

NP-hardness of the recognition of coordinated graphs

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C ₄, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. F.J. Soulignac is partially supported by UBACyT Grant X184, Argentina and CNPq under PROSUL project Proc. 490333/2004-4, Brazil.     

Random Graph Coverings I: General Theory and Graph Connectivity

In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number. Received June 21, 1999/Revised November 16, 2000 RID="*" ID="*" Work supported in part by grants from the Israel Academy of Aciences and the Binational Israel-US Science Foundation.     

Adjusted Interval Digraphs

Interval digraphs were introduced by West et al. They can be recognized in polynomial time and admit a characterization in terms of incidence matrices. Nevertheless, they do not have a forbidden structure characterization nor a low-degree polynomial recognition algorithm.We introduce a new class of ‘adjusted interval digraphs,’ obtained by a slight change in the definition. We show that, by contrast, these digraphs have a natural forbidden structure characterization, parallel to a characterization for undirected graphs, and admit a simple recognition algorithm. We relate adjusted interval digraphs to a list homomorphism problem. Each digraph H defines a corresponding list homomorphism problem L-HOM(H). We observe that if H is an adjusted interval digraph, then the problem L-HOM(H) is polynomial time solvable, and conjecture that for all other reflexive digraphs H the problem L-HOM(H) is NP-complete. We present some preliminary evidence for the conjecture, including a proof for the special case of semi-complete digraphs.     

A new closure concept preserving graph Hamiltonicity and based on neighborhood equivalence

A graph is Hamiltonian if it contains a cycle which goes through all vertices exactly once. Determining if a graph is Hamiltonian is known as an NP-complete problem, and no satisfactory characterization for these graphs has been found.In 1976, Bondy and Chvàtal introduced a way to get round the Hamiltonicity problem complexity by using a closure of the graph. This closure is a supergraph of G which is Hamiltonian iff G is. In particular, if the closure is the complete graph, then G is Hamiltonian. Since this seminal work, several closure concepts preserving Hamiltonicity have been introduced. In particular, in 1997, Ryjá?ek defined a closure concept for claw-free graphs based on local completion.Following a different approach, in 1974, Goodman and Hedetniemi gave a sufficient condition for Hamiltonicity based on the existence of a clique covering of the graph. This condition was recently generalized using the notion of Eulerian clique covering. In this context, closure concepts based on local completion are interesting since the closure of a graph contains more simplicial vertices than the graph itself, making the search for a clique covering easier.In this article, we introduce a new closure concept based on local completion which preserves the Hamiltonicity for every graph. Note that, moreover, the closure may be claw free even when the graph is not.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

The complexity of cover graph recognition for some varieties of finite lattices

We address the following decision problem: Instance: an undirected graphG. Problem: IsG a cover graph of a lattice? We prove that this problem is NP-complete. This extends results of Brightwell [5] and Ne?et?il and Rödl [12]. On the other hand, it follows from Alvarez theorem [2] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest: Given an integerl, l?3, there exists an algorithm which for a graphG withn vertices yields, in time polynomial inn, a graphH with the number of vertices polynomial inn, and satisfying girth(H)?l and χ(H)=χ(G).     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Zeta functions of line, middle, total graphs of a graph and their coverings

We consider the (Ihara) zeta functions of line graphs, middle graphs and total graphs of a regular graph and their (regular or irregular) covering graphs. Let L(G), M(G) and T(G) denote the line, middle and total graph of G, respectively. We show that the line, middle and total graph of a (regular and irregular, respectively) covering of a graph G is a (regular and irregular, respectively) covering of L(G), M(G) and T(G), respectively. For a regular graph G, we express the zeta functions of the line, middle and total graph of any (regular or irregular) covering of G in terms of the characteristic polynomial of the covering. Also, the complexities of the line, middle and total graph of any (regular or irregular) covering of G are computed. Furthermore, we discuss the L-functions of the line, middle and total graph of a regular graph G.     

On coloring problems with local constraints

We show complexity results for some generalizations of the graph coloring problem on two classes of perfect graphs, namely clique trees and unit interval graphs. We deal with the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand), and a problem generalizing both of them, the (γ, μ)-coloring problem (lower and upper bounds for the color on each vertex). We characterize the complexity of all those problems on clique trees of different heights, providing polytime algorithms for the cases that are easy. These results have two interesting corollaries: first, one can observe on clique trees of different heights the increasing complexity of the chain k-coloring, μ-coloring, (γ, μ)-coloring, list-coloring. Second, clique trees of height 2 are the first known example of a class of graphs where μ-coloring is polynomial time solvable and precoloring extension is NP-complete, thus being at the same time the first example where μ-coloring is polynomially solvable and (γ, μ)-coloring is NP-complete. Last, we show that the μ-coloring problem on unit interval graphs is NP-complete. These results answer three questions from [Ann. Oper. Res. 169(1) (2009), 3–16].     

Vertex-Disjoint Triangles in Claw-Free Graphs with Minimum Degree at Least Three

. Our main result is as follows: For any integer , if G is a claw-free graph of order at least and with minimum degree at least 3, then G contains k vertex-disjoint triangles unless G is of order and G belongs to a known class of graphs. We also construct a claw-free graph with minimum degree 3 on n vertices for each such that it does not contain k vertex-disjoint triangles. We put forward a conjecture on vertex-disjoint triangles in -free graphs. Received: November 21, 1996/Revised: Revised February 19, 1998     

Preperfect graphs

We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs.     

A Polynomial-Time Algorithm for Finding Regular Simple Paths in Outerplanar Graphs

Let G be a labeled directed graph with arc labels drawn from alphabet Σ, R be a regular expression over Σ, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of arc labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time.     

On the Sparsity Order of a Graph and Its Deficiency in Chordality

Given a graph G on n nodes, let denote the cone consisting of the positive semidefinite matrices (with real or complex entries) having a zero entry at every off-diagonal position corresponding to a non edge of G. Then, the sparsity order of G is defined as the maximum rank of a matrix lying on an extreme ray of the cone . It is known that the graphs with sparsity order 1 are the chordal graphs and a characterization of the graphs with sparsity order 2 is conjectured in [1] in the real case. We show in this paper the validity of this conjecture. Moreover, we characterize the graphs with sparsity order 2 in the complex case and we give a decomposition result for the graphs with sparsity order in both real and complex cases. As an application, these graphs can be recognized in polynomial time. We also indicate how an inequality from [17] relating the sparsity order of a graph and its minimum fill-in can be derived from a result concerning the dimension of the faces of the cone . Received August 31, 1998/Revised April 26, 2000     

Homomorphisms of Products of Graphs into Graphs Without Four Cycles

Given two graphs A and G, we write if there is a homomorphism of A to G and if there is no such homomorphism. The graph G is -free if, whenever both a and c are adjacent to b and d, then a = c or b = d. We will prove that if A and B are connected graphs, each containing a triangle and if G is a -free graph with and , then (here " denotes the categorical product). Received August 31, 1998/Revised April 19, 2000 RID="†" ID="†" Supported by NSERC of Canada Grant #691325.     

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.