Here is a Romanian translation of this web page (by Web Geek Science)
|
As a part of the 1992 -- 1993 Special Year on Combinatorial Optimization at DIMACS, László Lovász, Bruce Reed, and I organized a workshop on perfect graphs. The workshop took place at Princeton University on June 10--14, 1993. In February of that year, Bruce and I prepared a list of open problems, which was then sent to all the invited participants. The next version of the list, updated just before the workshop, and still available at
If you have
Vašek Chvátal
Related pages:
This collection is written for people with at least a basic knowledge of perfect graphs. Uninformed neophytes may look up the missing definitions on the web in Alexander Schrijver's lecture notes or in Jerry Spinrad's draft of a book on efficient graph representations etc. or in MathWorld. Books on perfect graphs include
1. Recognition of perfect graphs
2. Optimization in perfect graphs
3. Structure of partitionable graphs
4. The P4-structure and its relatives
5. Parity pairs and perfectly contractile graphs
6. Graphs without odd holes (and graphs without even holes)
7. Intersection graphs
8. q-perfect graphs
In November 2002, this section became obsolete: perfect graphs can be recognized in polynomial time. See
M. Chudnovsky, G. Cornuéjols, X. Liu, P.D. Seymour, and K. Vušković, Recognizing Berge Graphs, Combinatorica 25 (2005), 143--186.
Can these four optimization problems be solved for perfect graphs
by polynomial-time algorithms of purely combinatorial nature avoiding
the numerical instability of the ellipsoid method? The decomposition
theorem for perfect graphs does not -- or at least does not yet --
provide such algorithms; warm-up exercises consist of trying to
design such algorithms for restricted classes of perfect graphs. One
of these infinitely many warm-up problems is singled out here.
< in such a way that no
induced P4 with vertices a,b,c,d and edges
ab,bc,cd has a<b and d<c.
Chvátal (Perfectly ordered graphs. Topics on perfect
graphs, North-Holland Math. Stud., 88, North-Holland, Amsterdam-New
York, 1984, pp. 63--65. MR
86j:05059) has shown that, given a perfectly ordered
graph G and its coloring -- by some number k
of colors -- constructed by the familiar greedy algorithm, one can
find a clique of k vertices in G in
polynomial time; it follows that perfectly ordered graphs are
perfect.
Problem 2.1. Design a polynomial-time algorithm of purely combinatorial nature that, given a perfectly ordered graphG, constructs a largest stable set inG.
-1 vertices which meets
all cliques of size omega(G) and all stable sets of size
alpha(G). The following problem is an easier variation on a
conjecture contributed to the 1993 workshop by Gurvich and Temkin and
on two conjectures proposed by Bacsó, Boros, Gurvich, Maffray,
and Preissmann (On minimal imperfect graphs with circular
symmetry, J. Graph Theory 29 (1998),
209--225. MR
2000h:05116).
Conjecture 3.1. Every partitionable graph G with alpha(G)>2 and omega(G)>2One of the milestones in the development of our understanding of perfect graphs was the theorem of Lovász (A characterization of perfect graphs, J. Combinatorial Theory Ser. B 13 (1972), 95--98. MR 46 #8885) asserting that every minimal imperfect graph G has precisely
has a small transversal or else contains a hole of length five.
A partitionable graph without a small transversal has been constructed
by by Chvátal, Graham, Perold, and Whitesides (op.cit.). Its
vertices are 0,1,...,16; vertices i and
j are adjacent if and only if |i-j|
mod 17 is one of
1,3,4,5,12,13,14,16.
1 - 4 - 8 - 12 - 15 - 1
Helpful hints in the direction of Conjecture 3.1 are the results of
Bacsó, Boros, Gurvich, Maffray, and Preissmann (op.cit.); these
involve the construction of partitionable graphs with rotational
symmetries designed by Chvátal, Graham, Perold, and Whitesides
(op.cit.), which goes as follows.
Take any factorization
Bacsó, Boros, Gurvich, Maffray, and Preissmann (op. cit.) say that a CGPW graph is of Type 2 if it has both of the properties
A helpful result on small transversals (called the "Parent Lemma" in the paper of Bacsó, Boros, Gurvich, Maffray, and Preissmann) goes as follows. In a partitionable graph G, a clique C of size omega(G) is a mother of a vertex v if no clique of size omega(G) meets C in the single vertex v; a stable set S of size alpha(G) is a father of a vertex v if no stable set of size alpha(G) meets S in the single vertex v. Gurvich and Temkin (Berge's conjecture holds for rotational graphs.(Russian) Dokl. Akad. Nauk 332 (1993), 144--148. MR 94m:05156) and, independently, Bacsó proved that
if some vertex in a partitionable graph has both parents,
then the graph has a small transversal.
The following problem, related to Conjecture 3.1, has been contributed to the 1993 workshop by András Sebö.
Problem 3.2. True or false? If a partitionable graph G contains two cliques of size omega(G) with omega(G)-1 vertices in common and two stable sets of size alpha(G) with alpha(G)-1 vertices in common, then G has a small transversal.An affirmative solution of Problem 3.2 would sharpen the main result of Markosyan, Gasparyan, and Markosyan (On a conjecture of Berge, J. Combin. Theory Ser. B 56 (1992), 97--107. MR 93h:05078) and also that of Sebö ( Forcing colorations, and the perfect graph conjecture, Integer Programming and Combinatorial Optimization 2 (E. Balas, G. Cornuéjols, and R. Kannan, eds.), Mathematical Programming Society and Carnegie Mellon University, 1992).
Problem 3.3. Prove that, in every partitionable graph other than C5,From results of
every P4 extends into a P5 or the complement of a P5.
in every partitionable graph,
every P4 extends into a P5 or the complement of a P5 or a C5.
I(G) such that
G' is the complement of G, then
I(G)=I(G'),
I(G)=I(G'), then G and G'
are either both perfect or both imperfect
G could be expressed exclusively in terms of some such natural
invariant.The finest invariant with properties (i) and (ii) assigns to each
graph G the unordered pair consisting of G
and its complement; the coarsest invariant with properties (i) and
(ii) sets
I(G)=1 if G is perfect and
I(G)=0 if G is imperfect.
P4-structure of G; this
invariant is defined as the hypergraph whose vertex-set V is
vertex-set of G and whose edges are the subsets of
V that induce P4's in
G. For example, here are two graphs with the same
P4-structure,
{a,b,c,d}, {b,c,d,e}, {c,d,e,f},
{d,e,f,a}, {e,f,a,b}, {f,a,b,c}:
a b
o--------o a b c
/ \ o---------o---------o
/ \ | | |
/ \ | | |
f o o c | | |
\ / | | |
\ / | | |
\ / o---------o---------o
o--------o d e f
e d
Since P4 is a self-complementary graph, the
P4-structure of G has property
(i); Chvátal (A semistrong perfect graph conjecture.
Topics on perfect graphs, North-Holland Math. Stud., 88,
North-Holland, Amsterdam-New York, 1984, pp. 279--280. MR
86j:05119) conjectured and Reed (A semistrong perfect
graph theorem, J. Combin. Theory Ser. B 43
(1987), 223--240. MR
88g:05059) proved that it has property (ii) as well.Additional graph invariants with properties (i) and (ii), found by Chính Hoàng, are
G, defined as the hypergraph whose vertex-set
V is vertex-set of G and whose edges are the
subsets of V that induce C5 or
the paw (the graph with vertices a,b,c,d and edges
ab,ac,bc,cd) or the complement of the paw in
G (C. T. Hoàng, On the
disc-structure of perfect graphs. I. The co-paw-structure,
Proceedings of the Third International Conference on Graphs and
Optimization, GO-III (Leukerbad, 1998), Discrete Appl. Math.
94 (1999), 247--262. MR
2001a:05065);
G, defined as the hypergraph whose vertex-set
V is vertex-set of G and whose edges are the
subsets of V that induce C5 or
C4 or the complement of
C4 in G
(C. T. Hoàng, On the disc-structure of perfect
graphs. II. The co-C4-structure, Discrete
Math. 252 (2002), 141--159);
G, defined as the hypergraph whose vertex-set
V is vertex-set of G and whose edges are the
subsets of V that induce P3 or
the complement of P3 in G
(C. T. Hoàng, On the
co-P3-structure of perfect graphs, to appear in
SIAM J. Discrete Math.);
G, defined as the hypergraph whose vertex-set
V is vertex-set of G and whose edges are the
subsets of V that induce K3 or
the complement of K3 in G
(since K3,P3,co-P3, and
co-K3 are the only graphs with three vertices,
two graphs have the same
co-P3-structure if and only if
they have the same
co-K3-structure).
P4-structure
applies -- with suitable modifications -- to Hoàng's invariants
as well.
Let us define an odd ring as the 4-uniform hypergraph with vertices
u0, u1, ..., uk-1
k is odd and at least five and with the
k
edges
{ui+1, ui+2, ui+3, ui+4}
k. It is easy, if a
little tedious, to show that a graph is a Berge graph if and only if
its P4-structure contains no induced odd ring;
this fact led in the past to speculations about possible certificates,
elegant, easily verifiable, and expressed exclusively in terms of
4-uniform hypergraphs, that a prescribed
P4-structure contains no induced odd ring. Finding such a certificate is at least as difficult as the -- as
yet unsolved -- problem of showing that the class of Berge graphs
belongs to NP. A less ambitious program would be an attempt to
reformulate the decomposition
theorem for perfect graphs by Chudnovsky, Robertson, Seymour, and
Thomas exclusively in terms of
P4-structure.
The decomposition theorem asserts that
every Berge graph either belongs to one of five classes of basic Berge graphs, namely,(for definitions, see the paper by Chudnovsky, Robertson, Seymour, and Thomas); in her thesis, Chudnovsky showed that the stronger assertion with M-joins dropped remains valid. Do the remaining three structural faults admit natural counterparts formulated exclusively in terms ofor else it has one of four structural faults, namely,
- bipartite graphs,
- complements of bipartite graphs,
- line-graphs of bipartite graphs,
- complements of line-graphs of bipartite graphs,
- "double split graphs",
- 2-join,
- 2-join in the complement,
- M-join,
- a balanced skew partition
P4-structure?
The following two problems represent one attempt to state this question in precise terms.
Problem 4.1. Find a class C1 of 4-uniform hypergraphs such that
- the
P4-structure of a graph belongs to C1 if and only if it is theP4-structure of a (possibly different) graph such that this graph or its complement admits a 2-join- membership in C1 can be tested in polynomial time.
Problem 4.2. Find a class C2 of 4-uniform hypergraphs such thatIt is conceivable that these problems can be solved by building up on the following three results:
- the
P4-structure of a graph belongs to C2 if and only if it is theP4-structure of a (possibly different) graph that admits a balanced skew partition,- membership in C2 can be tested in polynomial time.
P4-structures of graphs,
P4-structure does not fit the
intuitive meaning of the expression "exclusively in terms of
P4-structure".
This class is defined in terms of a certain directed graph,
- the
P4-structure of every basic Berge graph belongs to C,- no 4-uniform hypergraph in C contains an induced odd ring,
- membership in C can be tested in polynomial time.
D6(H), associated with every 4-uniform hypergraph
H: C consists of all 4-uniform
hypergraphs H such that
The vertices of
Hcontains no induced ring with five vertices and- all strongly connected components of
D6(H)are bipartite.
D6(H) are all the ordered
6-tuples
(u1,u2,u3,u4,u5,u6)
H
such that the sub-hypergraph of H induced by the set
{u1,u2,u3,u4,u5,u6}
{u1,u2,u3,u4},
{u2,u3,u4,u5},
{u3,u4,u5,u6};
(u1,u2,u3,u4,u5,u6)
D6(H) to vertex
(v1,v2,v3,v4,v5,v6)
D6(H) if and only if
v1=u2, v2=u3,
v3=u4, v4=u5,
v5=u6.
Trivially, membership in C can be tested in
polynomial time; trivially, no 4-uniform hypergraph in
C contains an induced odd ring; a proof that the
P4-structure of every basic Berge graph
belongs to C is based on the following observation
(verified by exhaustive search and used also in the proof that a graph
is a Berge graph if and only if its
P4-structure contains no induced odd ring):
TheNow consider an arbitrary graphP4-structure of a graphFwith verticesconsists of hyperedges u1,u2,u3,u4,u5,u6{u1,u2,u3,u4}, {u2,u3,u4,u5}, {u3,u4,u5,u6}only if
Fis isomorphic (as an unlabeled graph) with one of the following six graphs:
F1is the pathP6;F2is the complement ofF1;F3consists of verticesa,b,c,d,e,fand edgesab,bc,cd,eb,fb,fc,fe;F4is the complement ofF3;F5consists of verticesa,b,c,d,e,fand edgesab,bc,cd,de,fb,fc;F6is the complement ofF5.
G
and let H denote its
P4-structure; we shall say that a vertex
(u1,u2,u3,u4,u5,u6)
D6(H) is of type i if
the subgraph of G induced by
{u1,u2,u3,u4,u5,u6}
Fi. The next observation
(also verified by exhaustive search and also used in
the proof that a graph is a Berge graph if and only if its
P4-structure contains no induced odd ring) is this:
Each vertex ofIt follows thatD6(H)with nonzero in-degree and nonzero out-degree has one of the following four properties:
- it is of type
1and all its neighbors are of type1,5,or6;- it is of type
2and all its neighbors are of type2,5,or6;- it is of type
3and all its neighbors are of type4;- it is of type
4and all its neighbors are of type3.
each strongly connected component ofD6(H)with at least two vertices has one of the following three properties:
- all of its vertices are of type
1;- all of its vertices are of type
2;- it is bipartite, all its vertices in one part of the bipartition are of type
3, and all its vertices in the other part of the bipartition are of type4.
Finally, assuming that G is a basic Berge graph, we shall
verify that all strongly connected components of
D6(H) are bipartite. Since
P4-structure of G is invariant
under complementation of G, we may distinguish between
three cases.
Case 1: G is bipartite.
Since F2 is not bipartite, we only need to
two-color each strongly connected component of
D6(H) whose vertices are of type
1. This can be done by giving each of these
vertices,
(u1,u2,u3,u4,u5,u6),
u1 in G.Case 2: G is the line-graph of a bipartite graph.
The two-coloring of the vertices of the bipartite graph induces a
two-coloring of the edges of G such that the two edges of
any induced P3 in G have distinct
colors. Since F2 is not a line-graph of a
bipartite graph, we only need to two-color each strongly connected
component of D6(H) whose vertices are of type
1. This can be done by giving each of these vertices,
(u1,u2,u3,u4,u5,u6),
u1u2 in G.Case 3: G is a double split graph.
By definition, G has 2m+2n (m,n>1)
distinct vertices,
a1,...,am, b1,...,bm,
c1,...,cn, d1,...,dn,
ai is adjacent to a bj
if and only if i=j,
ci is nonadjacent to a dj
if and only if i=j,
{ai,bi,cj,dj}
induces a P4.
(u1,u2,u3,u4,u5,u6)
D6(H) that is of type 1 must have
u1,u3,u4,u6
in
{a1,...,am,b1,...,bm}
u2,u5
in
{c1,...,cn,d1,...,dn};
1 are adjacent.
Since the complement of a double split graph is a double split graph, no two vertices of
type 2 are adjacent, either.Here are a few results on recognizing P4-structures of graphs:
P4-structures of trees,
P4-structures of line-graphs of bipartite
graphs,
P4-structures of bipartite graphs.
P4-structures of connected graphs whose
2-connected components are cliques.
P4-structures of graphs.
An even pair is a pair of vertices such that every
chordless path between them has an even number of
edges. J. Fonlupt and J.-P. Uhry (Transformations which
preserve perfectness and H-perfectness of graphs, Bonn Workshop
on Combinatorial Optimization (Bonn, 1980), Ann. Discrete Math., 16,
North-Holland, Amsterdam-New York, 1982, pp. 83--95. MR
84f:05076) and H. Meyniel (A new property of critical
imperfect graphs and some consequences, European
J. Combin. 8 (1987), 313--316. MR
88k:05082) proved that contracting an even pair
in a graph G (which means deleting both vertices of the
even pair, introducing a brand new vertex, and making the neighborhood
of this new vertex equal to the union of the neighborhoods of the two
deleted vertices) changes neither the clique number of G
nor the chromatic number of G.
M.E. Bertschi (Perfectly contractile graphs,
J. Combin. Theory Ser. B 50 (1990), 222--230. MR
91j:05042) defined an even-contractile graph as
any graph G for which there is a sequence
G0, G1, ..., Gk
G0=G,
Gt+1 arises by
contracting an even pair in Gt,
Gk is a clique
G such that all induced subgraphs of
G are even-contractile. (The results of Meyniel
guarantee that every perfectly contractile graph is perfect.)Hazel Everett and Bruce Reed contributed to the 1993 workshop a number of conjectures on even pairs and perfectly contractile graphs; two of them are singled out here. The odd stretcher in the first of them is any graph that consists of three vertex-disjoint triangles and three vertex-disjoint paths, each path having an odd number of edges and one endpoint in each of the two triangles. (In particular, the smallest odd stretcher is the antihole with six vertices.)
Conjecture 5.1. A graph is perfectly contractile if and only if it contains no odd hole, no antihole, and no odd stretcher.
Conjecture 5.2. Every perfectly contractile graph other than a clique contains an even pair whose contraction leaves the graph perfectly contractile.
Bienstock (On the complexity of testing for odd holes and induced odd paths, Discrete Math. 90 (1991), 85--92. MR 92m:68040a Corrigendum: Discrete Math. 102 (1992), 109. MR 92m:68040b) has proved that it is coNP-complete to determine if a graph contains an even pair. By analogy with the notion of en even pair, an odd pair is a pair of nonadjacent vertices such that every chordless path between them has an odd number of edges. The following two algorithmic problems are obvious.
Problem 5.3. Design a polynomial-time algorithm to determine
if a perfect graph contains an even pair.
Problem 5.4. Design a polynomial-time algorithm to determine
if a perfect graph contains an odd pair.
Other problems on path parity and perfection, including additional conjectures contributed to the 1993 workshop by Everett and Reed, can be found in
Problems 6.1--6.3 come from András Gyárfás (Problems from the world surrounding perfect graphs, Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Zastos. Mat. 19 (1987), 413--441. MR 89e:05089).
Problem 6.1. Prove the existence of a function g such thatGuoli Ding asked whether g(3)=4. His question has been answered in the affirmative by Robertson, Seymour, and Thomas, who provided a structural characterization of graphs without odd holes and without K4.
every graph G with no odd hole has chromatic number at most g(omega(G)).
Problem 6.2. For all positive integers k, prove the existence of a function gk such that every graph G with no odd hole longer than k has chromatic number at most gk(omega(G)).
Problem 6.3. For all positive integers k, prove the existence of a function hk such that every graph G with no hole longer than k has chromatic number at most hk(omega(G)).
Chính Hoàng and
Colin McDiarmid (On the divisibility of graphs, Discrete
Math. 242 (2002), 145--156. MR 1
874 761) say that a graph is 2-divisible
if, for each of its induced subgraphs F, the vertex-set
of F can be partitioned into subsets
S1 and S2 in such a
way that every largest clique in F meets both
S1 and S2. Trivially,
no odd hole is 2-divisible, and so every 2-divisible graph is
odd-hole-free; Hoàng and McDiarmid conjectured the converse:
Conjecture 6.4. Every odd-hole-free graph is 2-divisible.Hoàng and McDiarmid proved Conjecture 6.4. for claw-free graphs and noted that it also holds for graphs without K4 (since g(3)=4 in Problem 6.1).
Can something similar be said about graphs without even holes? The
notion of 2-divisibility generalizes: Hoàng and McDiarmid say
that a graph is k-divisible if, for each of its induced
subgraphs F, the vertex-set of F can be
partitioned into subsets S1,
S2, ..., Sk in such a
way that no Si contains a largest clique in
F.
Conjecture 6.5. (Hoàng) Every even-hole-free graph is 3-divisible.
Conjecture 6.6. (Hoàng) Every even-hole-free graphConjecture 6.6 implies Conjecture 6.5: more generally, ifGis colorable bycolors. 2·omega(G)-1
G is a graph and
k is an integer such that
k·(omega(G)-1) >= chi(G),
G is k-divisible.The following conjecture comes from Hayward and Reed (Forbidding holes and antiholes, in: Perfect Graphs (J.L. Ramírez-Alfonsín and B.A . Reed, eds.), Wiley, 2001, pp. 113--137. MR 1 861 360):
Conjecture 6.7. Every even-hole-free graph includes a vertex whose neighborhood can be partitioned into two cliques.Conjecture 6.7 implies Conjecture 6.6: more generally, if every induced subgraph of a graph
G includes a vertex of degree
at most t, then G is
t+1-colorable.Conforti, Cornuéjols, Kapoor, and Vušković (Even-hole-free graphs. II. Recognition algorithm. J. Graph Theory 40 (2002), 238--266) designed a polynomial algorithm to recognize even-hole-free graphs.
Problem 6.8. Design a polynomial algorithm to recognize odd-hole-free graphs.
Problems 7.1--7.6 were contributed by Zsolt Tuza before the 1993 workshop (see also Tuza, Perfect triangle families, Bull. London Math. Soc. 26 (1994), 321--324. MR 96b:05083).
Problem 7.1. For every (undirected) graph G, let H1(G) denote the graph whose vertices are the triangles in G, two vertices of H1(G) being adjacent if and only if the corresponding triangles in G share an edge.In a slightly related paper, Akiyama and Chvátal (Packing paths perfectly, Discrete Math. 85 (1990), 247--255. MR 92a:68114) studied graphs H'(G) whose vertices are (not necessarily induced) paths P3 in G, two vertices of H'(G) being adjacent if and only if the corresponding P3's in G share at least one vertex; they characterized (undirected) graphs G for which H'(G) is perfect. Another related paper is Lê, Perfect k-line graphs and k-total graphs, J. Graph Theory 17 (1993), 65--73. MR 94b:05083.
For which graphs G is H1(G) perfect?
Problem 7.2. For every directed graph G, let H2(G) denote the graph whose vertices are the transitive triangles in G, two vertices of H2(G) being adjacent if and only if the corresponding triangles in G share an arc.
For which graphs G is H2(G) perfect?
Problem 7.3. For every directed graph G, let H3(G) denote the graph whose vertices are the cyclic triangles in G, two vertices of H3(G) being adjacent if and only if the corresponding triangles in G share an arc.
For which graphs G is H3(G) perfect?
Problem 7.4. Charaterize graphs H such that
H=H1(G) for some graph G.
Problem 7.5. Charaterize graphs H such that
H=H2(G) for some directed graph G.
Problem 7.6. Charaterize graphs H such thatIf G is a planar oriented graph, then H3(G) is known to be (K4-e)-free Berge graph, and hence perfect.
H=H3(G) for some directed graph G.
Comment by Leizhen Cai: for each pair of graphs X and Y, Cai, Corneil and Proskurowski (A generalization of line graphs: (X,Y)-intersection graphs, J. Graph Theory 21 (1996), no. 3, 267--287. MR 96m:05164) defined the (X,Y)-intersection graph of a graph G as the graph whose vertices correspond to distinct induced subgraphs of G that are isomorphic to Y, and where two vertices are adjacent iff the intersection of the corresponding subgraphs contains an induced subgraph isomorphic to X. In this terminology, H1(G) is the (K2,K3)-intersection graphs of G. Cai, Corneil and Proskurowski have shown that the family of (X,Y)-intersection graphs is a subfamily of line-graphs of k-uniform hypergraphs, where k is the number of distinct induced copies of X in Y.
The following problems were contributed to the 1993 workshop by Claude Berge.
Problem 8.1 Characterize 2-perfect graphs.
Problem 8.2. Is it true that every minimal not-3-colorable 3-perfect graph is perfect?It is known that 2-perfect graphs are perfect and that the converse is false; it is known that parity graphs, balanced graphs, comparability graphs and cocomparability graphs are 2-perfect; see C. Berge, The q-perfect graphs. I. The case q=2. Sets, graphs and numbers (Budapest, 1991; L. Lovász, D. Miklos, and T. Szönyi, eds.), Colloq. Math. Soc. János Bolyai, 60, North-Holland, Amsterdam, 1992, pp.67--75. MR 94d:05110 and C. Berge, The q-perfect graphs. II.Combinatorics 92 (Catania, 1992), Matematiche (Catania) 47 (1992), 205--211 (1993). MR 95h:05126 and C. Berge, The q-perfect graphs. Graph theory, combinatorics, and algorithms, Vol. 1, 2 (Kalamazoo, MI, 1992), Wiley-Intersci. Publ., Wiley, New York, 1995, pp.47--62. MR 97c:05060.