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.     

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.     

Well-Quasi-Ordering versus Clique-Width: New Results on Bigenic Classes

Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in this case the answer is positive. The conjecture is known to hold for classes of graphs defined by a single forbidden induced subgraph H, as such graphs are well-quasi-ordered and are of bounded clique-width if and only if H is an induced subgraph of P ₄. For bigenic classes of graphs, i.e. ones defined by two forbidden induced subgraphs, there are several open cases in both classifications. In the present paper we obtain a number of new results on well-quasi-orderability of bigenic classes, each of which supports the conjecture.     

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.     

Graphs with two isomorphism classes of spanning unicyclic subgraphs

The graphs whose spanning unicyclic subgraphs partition into exactly two isomorphism classes are characterized.This work is a continuation of [6] where graphs with one isomorphism class of spanning unicyclic graphs are characterized. The analogous question for spanning trees was posed in [10] and graphs with one isomorphism class of spanning trees were characterized in [2], [3], [4], [7], [11] while graphs with two isomorphism classes of spanning trees were characterized in [4], [5]. Related topics are treated in [1], [8], [9].     

On the forbidden induced subgraph sandwich problem

We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length k is NP-complete. We prove that the sandwich problem corresponding to excluding K_r?e for fixed r is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.     

On minimal forbidden subgraph characterizations of balanced graphs

A {0, 1}-matrix is balanced if it contains no square submatrix of odd order with exactly two 1's per row and per column. Balanced matrices lead to ideal formulations for both set packing and set covering problems. Balanced graphs are those graphs whose clique-vertex incidence matrix is balanced.While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to some graph classes which also lead to polynomial time or even linear time recognition algorithms within the corresponding subclasses.     

Two forbidden induced subgraphs and well-quasi-ordering

It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P₄. However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k=2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.     

A Simple Linear-Time Recognition Algorithm for Weakly Quasi-Threshold Graphs

Weakly quasi-threshold graphs form a proper subclass of the well-known class of cographs by restricting the join operation. In this paper we characterize weakly quasi-threshold graphs by a finite set of forbidden subgraphs: the class of weakly quasi-threshold graphs coincides with the class of {P ₄, co-(2P ₃)}-free graphs. Moreover we give the first linear-time algorithm to decide whether a given graph belongs to the class of weakly quasi-threshold graphs, improving the previously known running time. Based on the simplicity of our recognition algorithm, we can provide certificates of membership (a structure that characterizes weakly quasi-threshold graphs) or non-membership (forbidden induced subgraphs) in additional ${{\mathcal O}(n)}$ time. Furthermore we give a linear-time algorithm for finding the largest induced weakly quasi-threshold subgraph in a cograph.     

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 any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009     

The isomorphism problem for classes of graphs closed under contraction

We consider the isomorphism problem for graphs in classes which, together with any graph, contain its connected induced subgraphs and graphs obtained by successive identifications of endpoints of edges. The main result is to establish sufficient conditions for the existence of a polynomial time algorithm testing graphs of such classes for isomorphism. It is shown that classes failing to satisfy these conditions are isomorphism-complete.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 147–177, 1988.     

Homogeneoys graphs

Let Γ be a finite graph with vertex set VΓ, and let U, V be arbitrary subsets of VΓ. Γ is homogeneoys (resp. ultrahomogeneous) if whenever the induced subgraphs 〈U〉, 〈V〉 are isomorphic, some isomorphism (resp. every isomorphism) of 〈U〉 onto 〈V〉 extends to an automorphism of Γ. We extend a theorem of Sheehan on ultrahomogeneous graphs to the homogeneous case, and complete his classification of ultrahomogenous graphs.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

On graphs whose Laplacian matrix’s multipartite separability is invariant under graph isomorphism

Normalized Laplacian matrices of graphs have recently been studied in the context of quantum mechanics as density matrices of quantum systems. Of particular interest is the relationship between quantum physical properties of the density matrix and the graph theoretical properties of the underlying graph. One important aspect of density matrices is their entanglement properties, which are responsible for many nonintuitive physical phenomena. The entanglement property of normalized Laplacian matrices is in general not invariant under graph isomorphism. In recent papers, graphs were identified whose entanglement and separability properties are invariant under isomorphism. The purpose of this note is to completely characterize the set of graphs whose separability is invariant under graph isomorphism. In particular, we show that this set consists of K_2,2 and its complement, all complete graphs and no other graphs.     

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.     

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.     

Automorphism groups of graphs and edge-contraction

If a class C of finite graphs is closed under contraction and forming subgraphs, and if every finite abstract group occurs as the automorphism group of some graph in C, then C contains all finite graphs (up to isomorphism). Also related results concerning automorphism groups of graphs on given surfaces are mentioned.     

Universal graphs and induced-universal graphs

We construct graphs that contain all bounded-degree trees on n vertices as induced subgraphs and have only cn edges for some constant c depending only on the maximum degree. In general, we consider the problem of determining the graphs, so-called universal graphs (or induced-universal graphs), with as few vertices and edges as possible having the property that all graphs in a specified family are contained as subgraphs (or induced subgraphs). We obtain bounds for the size of universal and induced-universal graphs for many classes of graphs such as trees and planar graphs. These bounds are obtained by establishing relationships between the universal graphs and the induced-universal graphs.     

Distance-hereditary graphs

Distance-hereditary graphs (sensu Howorka) are connected graphs in which all induced paths are isometric. Examples of such graphs are provided by complete multipartite graphs and ptolemaic graphs. Every finite distance-hereditary graph is obtained from K₁ by iterating the following two operations: adding pendant vertices and splitting vertices. Moreover, distance-hereditary graphs are characterized in terms of the distance function d, or via forbidden isometric subgraphs.     

Bidegreed graphs are edge reconstructible

An edge-deleted subgraph of a graph G is a subgraph obtained from G by the deletion of an edge. The Edge Reconstruction Conjecture asserts that every simple finite graph with four or more edges is determined uniquely, up to isomorphism, by its collection of edge-deleted subgraphs. A class of graphs is said to be edge reconstructible if there is no graph in the class with four or more edges that is not edge reconstructible. This paper proves that bidegreed graphs (graphs whose vertices all have one of two possible degrees) are edge reconstructible. The results are then generalized to show that all graphs that do not have three consecutive integers in their degree sequence are also edge reconstructible.