Wing-triangulated graphs are perfect

The wing-graph W(G) of a graph G has all edges of G as its vertices; two edges of G are adjacent in W(G) if they are the nonincident edges (called wings) of an induced path on four vertices in G. Hoàng conjectured that if W(G) has no induced cycle of odd length at least five, then G is perfect. As a partial result towards Hoàng's conjecture we prove that if W(G) is triangulated, then G is perfect. © 1997 John Wiley & Sons, Inc.     

Meyniel graphs are strongly perfect

Meyniel (Discrete Math.16 (1976), 339–342) proved that a graph is perfect whenever each of its odd cycles of length at least five has at least two chords. This result is strengthened by proving that every graph satisfying Meyniel's condition is strongly perfect (i.e., each of its induced subgraphs H contains a stable set which meets all the maximal cliques in H).     

Slightly triangulated graphs are perfect

A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C _k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;

1. G contains no chordless cycle with at least 5 vertices.
2. For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.

     

Series-parallel graphs are windy postman perfect

The windy postman problem is the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of an edge depends on the direction of traversal. Given an undirected graph G, we consider the polyhedron O(G) induced by a linear programming relaxation of the windy postman problem. We say that G is windy postman perfect if O(G) is integral. There exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. By considering a family of polyhedra related to O(G), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Win.     

Perfectly orderable graphs and almost all perfect graphs are kernelM-solvable

A graph is perfectly orderable if and only if it admits an acyclic orientation which does not contain an induced subgraph with verticesa, b, c, d and arcsab, bc, dc. Further a graph is called kernelM-solvable if for every direction of the edges (here pairs of symmetric, i.e. reversible, arcs are allowed) such that every directed triangle possesses at least two pairs of symmetric arcs, there exists a kernel, i.e. an independent setK of vertices such that every other vertex sends some arc towardsK. We prove that perfectly orderable graphs are kernelM-solvable. Using a deep result of Prömel and Steger we derive that almost all perfect graphs are kernelM-solvable.     

Transitive orientations in bull-reducible Berge graphs

A bull is a graph with five vertices r,y,x,z,s and five edges ry, yx, yz, xz, zs. A graph G is bull-reducible if every vertex of G lies in at most one bull of G. We prove that every bull-reducible Berge graph G that contains no antihole is weakly chordal, or has a homogeneous set, or is transitively orientable. This yields a fast polynomial time algorithm to color the vertices of such a graph exactly.     

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.     

Line perfect graphs

The concept of line perfection of a graph is defined so that a simple graph is line perfect if and only if its line graph is perfect in the usual sense. Line perfect graphs are characterized as those which contain no odd cycles of size larger than 3. Two well-know theorems of König for bipartite graphs are shown to hold also for line perfect graphs; this extension provides a reinterpretation of the content of these theorems.Supported by National Science Foundation Grants GK-42095 and ENG 76-09936.     

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.     

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.     

Berge graphs with chordless cycles of bounded length

A graph is called weakly triangulated if it contains no chordless cycle on five or more vertices (also called hole) and no complement of such a cycle (also called antihole). Equivalently, we can define weakly triangulated graphs as antihole-free graphs whose induced cycles are isomorphic either to C₃ or to C₄. The perfection of weakly triangulated graphs was proved by Hayward [Hayward, J Combin Theory B. 39 (1985), 200–208] and generated intense studies to efficiently solve, for these graphs, the classical NP-complete problems that become polynomial on perfect graphs. If we replace, in the definition above, the C₄ by an arbitrary C_p (p even, at least equal to 6), we obtain new classes of graphs whose perfection is shown in this article. In fact, we prove a more general result: for any even integer p ≥ 6, the graphs whose cycles are isomorphic either to C₃ or to one of C_p, C_p+2, …, C_{2p 6} are perfect. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 73–79, 1999     

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.     

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.     

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.     

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.     

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.