Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

A graph is clique-perfect if the cardinality of a maximum clique-independent set equals the cardinality of a minimum clique-transversal, for all its induced subgraphs. A graph G is coordinated if the chromatic number of the clique graph of H equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of cliqueperfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem,W₄,bull}-free, two superclasses of triangle-free graphs.     

On hereditary clique-Helly self-clique graphs

A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.     

Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. The clique-transversal number and clique-independence number of G are the sizes of a minimum clique-transversal and a maximum clique-independent set of G, respectively. A graph G is clique-perfect if these two numbers are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. In this paper, we present a partial result in this direction; that is, we characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs.     

Triangle-free strongly circular-perfect graphs

Zhu [X. Zhu, Circular-perfect graphs, J. Graph Theory 48 (2005) 186-209] introduced circular-perfect graphs as a superclass of the well-known perfect graphs and as an important χ-bound class of graphs with the smallest non-trivial χ-binding function χ(G)≤ω(G)+1. Perfect graphs have been recently characterized as those graphs without odd holes and odd antiholes as induced subgraphs [M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem, Ann. Math. (in press)]; in particular, perfect graphs are closed under complementation [L. Lovász, Normal hypergraphs and the weak perfect graph conjecture, Discrete Math. 2 (1972) 253-267]. To the contrary, circular-perfect graphs are not closed under complementation and the list of forbidden subgraphs is unknown.We study strongly circular-perfect graphs: a circular-perfect graph is strongly circular-perfect if its complement is circular-perfect as well. This subclass entails perfect graphs, odd holes, and odd antiholes. As the main result, we fully characterize the triangle-free strongly circular-perfect graphs, and prove that, for this graph class, both the stable set problem and the recognition problem can be solved in polynomial time.Moreover, we address the characterization of strongly circular-perfect graphs by means of forbidden subgraphs. Results from [A. Pêcher, A. Wagler, On classes of minimal circular-imperfect graphs, Discrete Math. (in press)] suggest that formulating a corresponding conjecture for circular-perfect graphs is difficult; it is even unknown which triangle-free graphs are minimal circular-imperfect. We present the complete list of all triangle-free minimal not strongly circular-perfect graphs.     

Infinite graphs with the least limiting eigenvalue greater than -2

Let λ(F) be the least eigenvalue of a finite graph F. The least limiting eigenvalue λ(G) of a connected infinite graph G is defined by λ(G)=inf_F{λ(F)}, where F runs over all finite induced subgraphs of G. In [4] and [5] it is proved that λ(G)⩾−2 if and only if G is a generalized line graph. In this paper all connected infinite graphs (thus all generalized line graphs) with λ(G)>−2 are characterized.     

Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. 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 equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W₄, bull}-free, both superclasses of triangle-free graphs.     

Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc () graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect graphs.     

The competition number of a graph and the dimension of its hole space

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between x and y if and only if there exists a vertex v in D such that (x,v) and (y,v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of G is the smallest number of such isolated vertices. In general, it is hard to compute the competition number k(G) for a graph G and it has been one of the important research problems in the study of competition graphs to characterize a graph by its competition number. Recently, the relationship between the competition number and the number of holes of a graph has been studied. A hole of a graph is a cycle of length at least 4 as an induced subgraph. In this paper, we conjecture that the dimension of the hole space of a graph is not smaller than the competition number of the graph. We verify this conjecture for various kinds of graphs and show that our conjectured inequality is indeed an equality for connected triangle-free graphs.     

A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

Locally finite homogeneous graphs

A connected graph G is said to be z-homogeneous if any isomorphism between finite connected induced subgraphs of G extends to an automorphism of G. Finite z-homogeneous graphs were classified in [17]. We show that z-homogeneity is equivalent to finite-transitivity on the class of infinite locally finite graphs. Moreover, we classify the graphs satisfying these properties. Our study of bipartite z-homogeneous graphs leads to a new characterization for hypercubes.     

Collapsible graphs and reductions of line graphs

A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].     

Partial Characterizations of Circular-Arc Graphs

A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to the following classes: diamond-free graphs, P₄-free graphs, paw-free graphs, and claw-free chordal graphs.     

Metric characterizations of proper interval graphs and tree-clique graphs

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When T is a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real line such that no interval contains another. We present here metric characterizations of proper interval graphs and extend them to tree-clique graphs. This is done by demonstrating “local” properties of tree-clique graphs with respect to the subgraphs induced by paths of a compatible tree. © 1996 John Wiley & Sons, Inc.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Distance-residual subgraphs

For a connected finite graph G and a subset V₀ of its vertex set, a distance-residual subgraph is a subgraph induced on the set of vertices at the maximal distance from V₀. Some properties and examples of distance-residual subgraphs of vertex-transitive, edge-transitive, bipartite and semisymmetric graphs are presented. The relations between the distance-residual subgraphs of product graphs and their factors are explored.     

A Min–Max Property of Chordal Bipartite Graphs with Applications

We show that if G is a bipartite graph with no induced cycles on exactly 6 vertices, then the minimum number of chain subgraphs of G needed to cover E(G) equals the chromatic number of the complement of the square of line graph of G. Using this, we establish that for a chordal bipartite graph G, the minimum number of chain subgraphs of G needed to cover E(G) equals the size of a largest induced matching in G, and also that a minimum chain subgraph cover can be computed in polynomial time. The problems of computing a minimum chain cover and a largest induced matching are NP-hard for general bipartite graphs. Finally, we show that our results can be used to efficiently compute a minimum chain subgraph cover when the input is an interval bigraph.     

Partial characterizations of circle graphs

A circle graph is the intersection graph of a family of chords on a circle. There is no known characterization of circle graphs by forbidden induced subgraphs that do not involve the notions of local equivalence or pivoting operations. We characterize circle graphs by a list of minimal forbidden induced subgraphs when the graph belongs to one of the following classes: linear domino graphs, P₄-tidy graphs, and tree-cographs. We also completely characterize by minimal forbidden induced subgraphs the class of unit Helly circle graphs, which are those circle graphs having a model whose chords have all the same length, are pairwise different, and satisfy the Helly property.     

Unique factorization of compositive hereditary graph properties

A graph property is any class of graphs that is closed under isomorphisms. A graph property P is hereditary if it is closed under taking subgraphs; it is compositive if for any graphs G1, G2 ∈ P there exists a graph G ∈ P containing both G1 and G2 as subgraphs. Let H be any given graph on vertices v1, . . . , vn, n ≥ 2. A graph property P is H-factorizable over the class of graph properties P if there exist P 1 , . . . , P n ∈ P such that P consists of all graphs whose vertex sets can be partitioned into n parts, possibly empty, satisfying: 1. for each i, the graph induced by the i-th non-empty partition part is in P i , and 2. for each i and j with i = j, there is no edge between the i-th and j-th parts if vi and vj are non-adjacent vertices in H. If a graph property P is H-factorizable over P and we know the graph properties P 1 , . . . , P n , then we write P = H [ P 1 , . . . , P n ]. In such a case, the presentation H[ P 1 , . . . , P n ] is called a factorization of P over P. This concept generalizes graph homomorphisms and (P 1 , . . . , P n )-colorings. In this paper, we investigate all H-factorizations of a graph property P over the class of all hered- itary compositive graph properties for finite graphs H. It is shown that in many cases there is exactly one such factorization.     

Clique-perfectness of complements of line graphs

The clique-transversal number τ_c(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number α_c(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation nor is a characterization by forbidden induced subgraphs known. Nevertheless, partial results in this direction have been obtained. For instance, in [Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discrete Appl. Math. 156 (2008), pp. 1058–1082], a characterization of those line graphs that are clique-perfect is given in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect, also by means of minimal forbidden induced subgraphs. This implies an O(n²) time algorithm for deciding the clique-perfectness of complements of line graphs and, for those that are clique-perfect, finding α_c and τ_c.     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005