Recursive generation of partitionable graphs

Results of Lovász (1972) and Padberg (1974) imply that partitionable graphs contain all the potential counterexamples to Berge's famous Strong Perfect Graph Conjecture. A recursive method of generating partitionable graphs was suggested by Chvátal, Graham, Perold, and Whitesides (1979). Results of Seb? (1996) entail that Berge's conjecture holds for all the partitionable graphs obtained by this method. Here we suggest a more general recursion. Computer experiments show that it generates all the partitionable graphs with ω=3,α ≤ 9 (and we conjecture that the same will hold for bigger α, too) and many but not all for (ω,α)=(4,4) and (4,5). Here, α and ω are respectively the clique and stability numbers of a partitionable graph, that is the numbers of vertices in its maximum cliques and stable sets. All the partitionable graphs generated by our method contain a critical ω‐clique, that is an ω‐clique which intersects only 2ω?2 other ω‐cliques. This property might imply that in our class there are no counterexamples to Berge's conjecture (cf. Seb? (1996)), however this question is still open. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 259–285, 2002     

A counterexample to the bold conjecture

A pair of vertices (x,y) of a graph G is an o-critical pair if o(G + xy) > o(G), where G + xy denotes the graph obtained by adding the edge xy to G and o(H) is the clique number of H. The o-critical pairs are never edges in G. A maximal stable set S of G is called a forced color class of G if S meets every o-clique of G, and o-critical pairs within S form a connected graph. In 1993, G. Bacsó raised the following conjecture which implies the famous Strong Perfect Graph Conjecture: If G is a uniquely o-colorable perfect graph, then G has at least one forced color class. This conjecture is called the Bold Conjecture. Here we show a simple counterexample to it. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 165–168, 1997     

Families of graphs complete for the strong perfect graph Conjecture

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true iff it is true on these restricted families. These appear to be the first results of this type.     

On the strong perfect graph conjecture

A graph G is perfect if for every induced subgraph H of G the chromatic number χ(H) equals the largest number ω(H) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement G¯ contains an odd chordless cycle of length at least 5. Its resolution has eluded researchers for more than 20 years. We prove that the conjecture is true for a class of graphs that we describe by forbidden configurations.     

On the Structure of Bull-Free Perfect Graphs, 2: the Weakly Chordal Case

 A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. A graph is perfectly orderable if it admits an ordering such that the greedy sequential method applied on this ordering produces an optimal coloring for every induced subgraph. Chvátal conjectured that every bull-free graph with no odd hole or antihole is perfectly orderable. In a previous paper we studied the structure of general bull-free perfect graphs, and reduced Chvátal's conjecture to the case of weakly chordal graphs. Here we focus on weakly chordal graphs, and we reduce Chvátal's conjecture to a restricted case. Our method lays out the structure of all bull-free weakly chordal graphs. These results have been used recently by Hayward to establish Chvátal's conjecture for this restricted case and therefore in full. Received: November 26, 1997?Final version received: February 27, 2001     

Chair-Free Berge Graphs Are Perfect

A graph G is called Berge if neither G nor its complement contains a chordless cycle with an odd number of nodes. The famous Berge’s Strong Perfect Graph Conjecture asserts that every Berge graph is perfect. A chair is a graph with nodes {a, b, c, d, e} and edges {ab, bc, cd}, eb. We prove that a Berge graph with no induced chair (chair-free) is perfect or, equivalently, that the Strong Perfect Graph Conjecture is true for chair-free graphs.     

Reductions of the graph reconstruction conjecture

In this note we shall show that the Graph Reconstruction Conjecture (also called the Kelly-Ulam conjecture [1, p. 11]) is equivalent to a conjecture about the algebraic properties of certain directed trees and their homomorphic images. We shall show the the Greph Reconstruction Conjecture is equivalent to recognizing the (abstract) group of a graph from the tree (generalized “deck”) of the graph.     

Proof of Ding’s conjecture on maximal stable sets and maximal cliques in planar graphs

X. Deng et al. proved Chvātal＇s conjecture on maximal stable sets and maximal cliques in graphs. G. Ding made a conjecture to generalize Chvátal＇s conjecture. The purpose of this paper is to prove this conjecture in planar graphs and the complement of planar graphs.     

A generalization of simplicial elimination orderings

We consider the class of graphs where every induced subgraph possesses a vertex whose neighborhood has no P₄ and no 2K₂. We prove that Berge's Strong Perfect Graph Conjecture holds for such graphs. The class generalizes several well-known families of perfect graphs, such as triangulated graphs and bipartite graphs. Testing membership in this class and computing the maximum clique size for a graph in this class is not hard, but finding an optimal coloring is NP-hard. We give a polynomial-time algorithm for optimally coloring the vertices of such a graph when it is perfect. © 1996 John Wiley & Sons, Inc.     

On classes of minimal circular-imperfect graphs

Circular-perfect graphs form a natural superclass of perfect graphs: on the one hand due to their definition by means of a more general coloring concept, on the other hand as an important class of χ-bound graphs with the smallest non-trivial χ-binding function χ(G)?ω(G)+1.The Strong Perfect Graph Conjecture, recently settled by Chudnovsky et al. [The strong perfect graph theorem, Ann. of Math. 164 (2006) 51-229], provides a characterization of perfect graphs by means of forbidden subgraphs. It is, therefore, natural to ask for an analogous conjecture for circular-perfect graphs, that is for a characterization of all minimal circular-imperfect graphs.At present, not many minimal circular-imperfect graphs are known. This paper studies the circular-(im)perfection of some families of graphs: normalized circular cliques, partitionable graphs, planar graphs, and complete joins. We thereby exhibit classes of minimal circular-imperfect graphs, namely, certain partitionable webs, a subclass of planar graphs, and odd wheels and odd antiwheels. As those classes appear to be very different from a structural point of view, we infer that formulating an appropriate conjecture for circular-perfect graphs, as analogue to the Strong Perfect Graph Theorem, seems to be difficult.     

On a Class of P5-Free Graphs

A graph G is perfect in the sense of Berge if for every induced subgraph G′ of G, the chromatic number χ(G′) equals the largest number ω(G′) of pairwise adjacent vertices in G′. The Strong Perfect Graph Conjecture asserts that a graph G is perfect if, and only if, neither G nor its complement ? contains an odd chordless cycle of length at least five. We prove that the conjecture is true for a class of P₅-free graphs.     

On the strong circular 5‐flow conjecture

The Strong Circular 5‐flow Conjecture of Mohar claims that each snark—with the sole exception of the Petersen graph—has circular flow number smaller than 5. We disprove this conjecture by constructing an infinite family of cyclically 4‐edge connected snarks whose circular flow number equals 5. © 2006 Wiley Periodicals, Inc. J Graph Theory     

A survey of solved problems and applications on bandwidth,edgesum, and profile of graphs

This article provides a survey of results on the exact bandwidth, edgesum, and profile of graphs. A bibliography of work in these areas is provided. The emphasis is on composite graphs. This may be regarded as an update of the original survey of solved bandwidth problems by Chinn, Chvátalová, Dewdney, and Gibbs [10] in 1982. Also several of the application areas involving these graph parameters are described. © John & Sons, Inc. Graph Theory 31: 75–94, 1999     

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.     

On the structure of bull-free perfect graphs

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0     

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.     

Short proofs of classical theorems

We give proofs of Ore's theorem on Hamilton circuits, Brooks' theorem on vertex coloring, and Vizing's theorem on edge coloring, as well as the Chvátal-Lovász theorem on semi-kernels, a theorem of Lu on spanning arborescences of tournaments, and a theorem of Gutin on diameters of orientations of graphs. These proofs, while not radically different from existing ones, are perhaps simpler and more natural. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 159–165, 2003     

Compatible path-cycle-decompositions of plane graphs

Sabidussi's Conjecture states that given an Euler trail T in a connected Euler graph, there always exists a cycle decomposition S such that consecutive edges of T belong to different cycles in S. This conjecture has been solved in a generalized form for planar Euler graphs. A similar result for arbitrary planar graphs is the content of this paper.     

On Toughness and Hamiltonicity of 2K2‐Free Graphs

The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K₂‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K₂‐free graphs.     

Great-circle tree thrackles

A thrackle is a graph drawing in which every pair of edges meets exactly once. Conway's Thrackle Conjecture states that the number of edges of a thrackle cannot exceed the number of its vertices. Cairns et al. (2015) [1] prove that the Thrackle Conjecture holds for great-circle thrackles drawn on the sphere. They also posit that Conway's Thrackle Conjecture can be restated to say that a graph can be drawn as a thrackle drawing in the plane if and only if it admits a great-circle thrackle drawing. We demonstrate that the class of great-circle thrackleable graphs excludes some trees. Thus the informal conjecture from Cairns et al. (2015) [1] is not equivalent to the Thrackle Conjecture.