Critical perfect graphs and perfect 3-chromatic graphs

This paper builds on results based on D. R. Fulkerson's antiblocking polyhedra approach to perfect graphs to obtain information about critical perfect graphs and related clique-generated graphs. Then we prove that Berge's Strong Perfect Graph Conjecture is valid for 3-chromatic graphs.     

Trivially perfect graphs

An undirected graph is trivially perfect if for every induced subgraph the stability number equals the number of (maximal) cliques. We characterize the trivially perfect graphs as a proper subclass of the triangulated graphs (thus disproving a claim of Buneman [3]), and we relate them to some well-known classes of perfect graphs.     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

Random perfect graphs

We investigate the asymptotic structure of a random perfect graph P_n sampled uniformly from the set of perfect graphs on vertex set . Our approach is based on the result of Prömel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly. We show that the distribution of the maximum of the stability number and clique number is close to a concentrated distribution L(n) which plays an important role in our generation method. We also prove that the probability that P_n contains any given graph H as an induced subgraph is asymptotically 0 or or 1. Further we show that almost all perfect graphs are 2‐clique‐colorable, improving a result of Bacsó et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity equal to their minimum degree; they are almost all in class one (edge‐colorable using Δ colors, where Δ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphon .     

Neighborhood perfect graphs

The notion of neighborhood perfect graphs is introduced here as follows. Let G be a graph, α_N(G) denote the maximum number of edges such that no two of them belong to the same subgraph of G induced by the (closed) neighborhood of some vertex; let ϱ_N(G) be the minimum number of vertices whose neighborhood subgraph cover the edge set of G. Then G is called neighborhood perfect if ϱ_N(G′) = α_N(G′) holds for every induced subgraph G′ of G. It is expected that neighborhood perfect graphs are perfect also in the sense of Berge. We characterized here those chordal graphs which are neighborhood perfect. In addition, an algorithm to computer ϱ_N(G) = α_N(G) is given for interval graphs.     

Square-free perfect graphs

We prove that square-free perfect graphs are bipartite graphs or line graphs of bipartite graphs or have a 2-join or a star cutset.     

Strongly perfect infinite graphs

An infinite graph G is calledstrongly perfect if each induced subgraph ofG has a coloring (C _i :i ∈I) and a clique meeting each colorC _i . A conjecture of the first author and V. Korman is that a perfect graph with no infinite independent set is strongly perfect. We prove the conjecture for chordal graphs and for their complements. The research was begun at the Sonderforschungsbereich 343 at Bielefeld University and supported by the Fund for the Promotion of Research at the Technion.     

Classes of perfect graphs

The strong perfect graph conjecture, suggested by Claude Berge in 1960, had a major impact on the development of graph theory over the last 40 years. It has led to the definitions and study of many new classes of graphs for which the strong perfect graph conjecture has been verified. Powerful concepts and methods have been developed to prove the strong perfect graph conjecture for these special cases. In this paper we survey 120 of these classes, list their fundamental algorithmic properties and present all known relations between them.     

Decomposition of perfect graphs

We describe composition and decomposition schemes for perfect graphs, which generalize all recent results in this area, e.g., the amalgam and the 2-amalgam split. Our approach is based on the consideration of induced cycles and their complements in perfect graphs (as opposed to the consideration of cycles for defining biconnected or 3-connected graphs). Our notion of 1-inseparable graphs is “parallel” to that of biconnected graphs in that different edges in different inseparable components of a graph are not contained in any induced cycle or any complement of an induced cycle. Furthermore, in a special case which generalizes the join operation, this definition is self-complementary in a natural fashion. Our 2-composition operation, which only creates even induced cycles in the composed graphs, is based on two perfection-preserving vertex merge operations on perfect graphs. As a by-product, some new properties of minimally imperfect graphs are presented.     

Norms and perfect graphs

The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods.In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.This is a written account of an invited lecture delivered by the second author on occasion of the 12. Symposium on Operations Research, Passau, 9.–11. 9. 1987.     

Uniquely colorable perfect graphs

This paper defines the concept of sequential coloring. If G or its complement is one of four major types of perfect graphs, G is shown to be uniquely k-colorable it and only if it is sequentially k-colorable. It is conjectured that this equivalence is true for all perfect graphs. A potential role for sequential coloring in verifying the Strong Perfect Graph Conjecture is discussed. This conjecture is shown to be true for strongly sequentially colorable graphs.     

Star-cutsets and perfect graphs

We first establish a certain property of minimal imperfect graphs and then use it to generate large classes of perfect graphs.     

Recognizing bull-free perfect graphs

A bull is the graph obtained from a triangle by adding two pendant vertices adjacent to distinct vertices of the triangle. Chvátal and Sbihi showed that the strong perfect graph conjecture holds for Bull-free graphs. We give a polynomial time recognition algorithm for Bull-free perfect graphs.     

Progress on perfect graphs

 A graph is perfect if for every induced subgraph, the chromatic number is equal to the maximum size of a complete subgraph. The class of perfect graphs is important for several reasons. For instance, many problems of interest in practice but intractable in general can be solved efficiently when restricted to the class of perfect graphs. Also, the question of when a certain class of linear programs always have an integer solution can be answered in terms of perfection of an associated graph. In the first part of the paper we survey the main aspects of perfect graphs and their relevance. In the second part we outline our recent proof of the Strong Perfect Graph Conjecture of Berge from 1961, the following: a graph is perfect if and only if it has no induced subgraph isomorphic to an odd cycle of length at least five, or the complement of such an odd cycle. Received: December 19, 2002 / Accepted: April 29, 2003 Published online: May 28, 2003 Key words. Berge graph – perfect graph – skew partition Mathematics Subject Classification (1991): 05C17     

Cycle-perfect graphs are perfect

The cycle graph of a graph G is the edge intersection graph of the set of all the induced cycles of G. G is called cycle-perfect if G and its cycle graph have no chordless cycles of odd length at least five. We prove the statement of the title. © 1996 John Wiley & Sons, Inc.     

On critically perfect graphs

A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well-known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, and study operations preserving critical perfectness. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 394–404, 1999     

On line perfect graphs

Line-perfect graphs have been defined by L.E. Trotter as graphs whose line-graphs are perfect. They are characterized by the property of having no elementary odd cycle of size larger than 3. L.E. Trotter showed constructively that the maximum cardinality of a set of mutually non-adjacent edges (matching) is equal to the minimum cardinality of a collection of sets of mutually adjacent edges which cover all edges.The purpose of this note is to give an algorithmic proof that the chromatic index of these graphs is equal to the maximum cardinality of a set of mutually adjacent edges.     

Wings and perfect graphs

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of vertices such that G — C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. V. Chvátal proposed to call a graph unbreakable if neither G nor its complement contain a star-cutset. We establish several properties of unbreakable graphs using the notions of wings and saturation. In particular, we obtain seven equivalent versions of the Strong Perfect Graph Conjecture.