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.     

Circular-imperfection of triangle-free graphs

Circular-perfect graphs form a natural superclass of the well-known perfect graphs by means of a more general coloring concept.For perfect graphs, a characterization by means of forbidden subgraphs was recently settled by Chudnovsky et al. [Chudnovsky, M., N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics 164 (2006) 51–229]. It is, therefore, natural to ask for an analogous characterization for circular-perfect graphs or, equivalently, for a characterization of all minimally circular-imperfect graphs.Our focus is the circular-(im)perfection of triangle-free graphs. We exhibit several different new infinite families of minimally circular-imperfect triangle-free graphs. This shows that a characterization of circular-perfect graphs by means of forbidden subgraphs is a difficult task, even if restricted to the class of triangle-free graphs. This is in contrary to the perfect case where it is long-time known that the only minimally imperfect triangle-free graphs are the odd holes [Tucker, A., Critical Perfect Graphs and Perfect 3-chromatic Graphs, J. Combin. Theory (B) 23 (1977) 143–149].     

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.     

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.     

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.     

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 minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

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     

Minimal non-neighborhood-perfect graphs

Neighborhood-perfect graphs form a subclass of the perfect graphs if the Strong Perfect Graph Conjecture of C. Berge is true. However, they are still not shown to be perfect. Here we propose the characterization of neighborhood-perfect graphs by studying minimal non-neighborhood-perfect graphs (MNNPG). After presenting some properties of MNNPGs, we show that the only MNNPGs with neighborhood independence number one are the 3-sun and 3K₂. Also two further classes of neighborhood-perfect graphs are presented: line-graphs of bipartite graphs and a 3K₂-free cographs. © 1996 John Wiley & Sons, Inc.     

Partitionable graphs,circle graphs,and the berge strong perfect graph conjecture

Partitionable graphs have been studied by a number of authors in conjunction with attempts at proving the Berge Strong Perfect Graph Conjecture (SPGC). We give some new properties of partitionable graphs which can be used to give a new proof that the SPGC holds for K_1,3-free graphs. Finally, we will show that the SPGC also holds for the class of circle graphs.     

Algorithms for finding an induced cycle in planar graphs

In this paper, we consider the problem of finding an induced cycle passing through k given vertices, which we call the induced cycle problem. The significance of finding induced cycles stems from the fact that a precise characterization of perfect graphs would require understanding the structure of graphs without an odd induced cycle and its complement. There has been huge progress in the recent years, especially, the Strong Perfect Graph Conjecture was solved in [6]. Concerning recognition of perfect graphs, there had been a long-standing open problem for detecting an odd hole and its complement, and finally this was solved in [4].     

Graphical properties related to minimal imperfection

Say that graph G is partitionable if there exist integers α?2, ω? 2, such that |V(G)| ≡ αω + 1 and for every υ?V(G) there exist partitions of V(G)\ υ into stable sets of size α and into eliques of size ω. An immediate consequence of Lovász' characterization of perfect graphs is that every minimal imperfect graph G is partitionable with α ≡ α (G) andω ≡ ω(G).Padberg has shown that in every minimal imperfect graph G the cliques and stable sets of maximum size satisfy a series of conditions that reflect extraordinary symmetry G. Among these conditions are: the number of cliques of size ω(G) is exactly |V(G)|; the number of stable sets of size α(G) is exactly |V(G)|: every vertex of G is contained in exactly ω(G) cliques of size ω(G) and α(G) stable sets of size α(G): for every clique Q (respectively, stable set S) of maximum size there is a unique stable set S (clique O) of maximum size such that Q∩S ≡ Ø.Let C_n^k denote the graph whose vertices can be enumerated as υ₁,…,υ_n in such a way that υ₁ and υ₁ are adjacent in G if and only if i and j differ by at most k, modulo n. Chvátal has shown that Berge's Strong Perfect graph Conjecture is equivalent to the conjecture that if G is minimal imperfect with α(G) ≡ αandω(G) ≡ ω, then G has a spanning subgraph isomorphic to C_αω+1^ω. Padberg's conditions are sufficiently restrictive to suggest the possibility of establishing the Strong Perfect Graph Conjecture by proving that any graph G satisfying these conditions must contain a spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ αandω(G) ≡ ω. It is shown here, using only elementary linear algebra, that all partitionable graphs satisfy Padberg's conditions, as well as additional properties of the same spirit. Then examples are provided of partitionable graphs which contain no spanning subgraph isomorphic to C_αω+1^ω, whereα(G) ≡ α and ω(G) ≡ ω.     

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.     

A reduction procedure for coloring perfect K4-free graphs

This paper presents an algorithmic proof of the validity of the Strong Perfect Graph Conjecture for graphs whose largest clique is a triangle. The proof leads to an O(n³) algorithm to 3-color such graphs. In the process, a method is presented to contract a perfect graph into a set of smaller perfect graphs that are (K₄-e)-free.     

Relative colorings of graphs

In this paper, the notion of relative chromatic number χ(G, H) for a pair of graphs G, H, with H a full subgraph of G, is formulated; namely, χ(G, H) is the minimum number of new colors needed to extend any coloring of H to a coloring of G. It is shown that the four color conjecture (4CC) is equivalent to the conjecture (R4CC) that χ(G, H) ≤ 4 for any (possibly empty) full subgraph H of a planar graph G and also to the conjecture (CR3CC) that χ(G, H) ≤ 3 if H is a connected and nonempty full subgraph of planar G. Finally, relative coloring theorems on surfaces other than the plane or sphere are proved.     

Odd cycles and matrices with integrality properties

A cycle of a bipartite graphG(V⁺, V^?; E) is odd if its length is 2 (mod 4), even otherwise. An odd cycleC is node minimal if there is no odd cycleC′ of cardinality less than that ofC′ such that one of the following holds:C′ ∩V ⁺ ?C ∩V ⁺ orC′ ∩V ^? ?C ∩V ^?. In this paper we prove the following theorem for bipartite graphs: For a bipartite graphG, one of the following alternatives holds:

-All the cycles ofG are even.

-G has an odd chordless cycle.

-For every node minimal odd cycleC, there exist four nodes inC inducing a cycle of length four.

-An edge (u, v) ofG has the property that the removal ofu, v and their adjacent nodes disconnects the graphG.

To every (0, 1) matrixA we can associate a bipartite graphG(V⁺, V^?; E), whereV ⁺ andV ^? represent respectively the row set and the column set ofA and an edge (i,j) belongs toE if and only ifa _ij = 1. The above theorem, applied to the graphG(V⁺, V^?; E) can be used to show several properties of some classes of balanced and perfect matrices. In particular it implies a decomposition theorem for balanced matrices containing a node minimal odd cycleC, having the property that no four nodes ofC induce a cycle of length 4. The above theorem also yields a proof of the validity of the Strong Perfect Graph Conjecture for graphs that do not containK ₄?e as an induced subgraph.     

Coloring perfect (K4 − e)-free graphs

This note proves the Strong Perfect Graph Conjecture for (K₄ − e)-free graphs from first principles. The proof directly yields an O(pn²) algorithm for p-coloring a perfect (K₄ − e)-free graph.     

On the domination number of the generalized Petersen graphs

Graph domination numbers and algorithms for finding them have been investigated for numerous classes of graphs, usually for graphs that have some kind of tree-like structure. By contrast, we study an infinite family of regular graphs, the generalized Petersen graphs G(n). We give two procedures that between them produce both upper and lower bounds for the (ordinary) domination number of G(n), and we conjecture that our upper bound ⌈3n/5⌉ is the exact domination number. To our knowledge this is one of the first classes of regular graphs for which such a procedure has been used to estimate the domination number.     

Polyhedral results on the stable set problem in graphs containing even or odd pairs

Mathematical Programming - Even and odd pairs are important tools in the study of perfect graphs and were instrumental in the proof of the Strong Perfect Graph Theorem. We suggest that such pairs...