# New trends on structural graph theory (10w5121)

Arriving in Banff, Alberta Sunday, September 5 and departing Friday September 10, 2010

## Organizers

Ken-ichi Kawarabayashi (National Institute of Informatics)

Bojan Mohar (Simon Fraser University)

Bruce Reed (McGill University)

Paul Seymour (Princeton University)

## Objectives

Two of the most successful projects in graph theory are the proof of the strong perfect graphs and Graph Minors project and its applications and extensions.

Perfect graphs include many important families of graphs, and serve to unify results relating colorings and clique problems in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time (Grotschel, Lovasz and Schrijver 1988). In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs.

Berge conjectured that a graph is perfect if an only if no induced subgraph of it is an cycle of odd length at least five (which is called an odd hole), or the complement of one (which is called "odd anti-hole"). Today such graphs are called Berge graphs. The main part of the recent groundbreaking proof of the

Berge conjecture (by Chudnovsky, Robertson, Seymour and Thomas) was a more general theorem that describes the structure of all Berge graphs. More precisely, it was proved that every Berge graph either belongs to one of a few well understood families of basic graphs, or admits a certain decomposition (this was conjectured earlier by Conforti, Cornuejols and Vuskovic). Having obtained this explicit structural result for all Berge graphs, one was able to verify that all of them are perfect. (The other directions of Berge's conjecture is easy, because odd cycles and their complements are not perfect, and every induced subgraph of a perfect graph is). This is now called "The Strong Perfect Graph Theorem".

Recently, Chudnovsky and Seymour have developed the method and techniques used in the proof of Berge' conjecture, and given some fundamental results in this area. However, there are new problems still left in this area. In this workshop, we shall focus on the following problems.

1. Erdos-Hajnal Conjecture

This conjecture claims the following:

For every graph H, there exists a constant t = t(H) > 0, such that if G is an H-free graph, then G contains either a clique or a stable set of size $|V(G)|^t$.

This is concerned with a same kind of the question for perfect graphs, namely whether forbidding a certain induced subgraph has a global effect on a graph.

A recent structural result of Chudnovsky and Seymour allowed to solve a special case of Erdos-Hajnal conjecture, where H is a "bull" graph. The bull graph was one of the smallest subgraph for which the conjecture had not been known, and thus structure theory provided an interesting test case.

2. Building Perfect Graphs

The theorem by Chudnovsky, Robertson Seymour, and Thomas is that every Berge graph either belongs to one of a few well understood families of basic graphs, or admits a certain decomposition (this was conjectured earlier by Conforti, Cornuejols and Vuskovic). Having obtained this explicit structural result for all Berge graphs, one was able to verify that all of them are perfect. But this structure theorem does not tell us how to construct perfect graphs. In particular, one of the ingredients for the decomposition, namely, the skew-partition is a problem, because it may not preserve Berge graphs. So it would be nice if one could get a construction of Berge graphs.

3. Coloring perfect graphs.

The above mentioned result by Grotschel, Lovasz & Schrijver gives rise to a polynomial time algorithm to give an optimal coloring of perfect graphs, but that uses polyhedral method and real numbers. So there should be a "combinatorial" algorithm. This is connected to the second question. Since we do not know how to construct perfect graphs, so, currently, we do not know any combinatorial polynomial time algorithm to find an optimal coloring of a given perfect graph.

4. Recognizing odd holes.

The problem of recognizing Berge graphs is in co-NP (Lovasz 1983), but it was not known whether or not it is in P until after the proof of the Strong Perfect Graph Theorem appeared. (A polynomial time algorithm was discovered by Chudnovsky, Cornuejols, Liu, Seymour, and Vuskovic shortly afterwards, independent of the Strong Perfect Graph Theorem.) Thus one can test whether or not a given graph contains either an odd hole or an anti odd hole in polynomial time. But one major problem in this area is whether or not there is a polynomial time algorithm to recognize an odd hole. This is still open, although there is a polynomial time algorithm to recognize an even-hole (by Chudnovsky, Kawarabayashi and Seymour, and Conforti, Cornuejols, Vuskovic).

5. Construction of F-free graphs.

Recently, Chudnovsky and Seymour managed to give a construction for all claw-free graphs. As in the third question, we do not know how to construct perfect graphs(that is, graphs without odd holes and anti odd holes). Chudnovsky recently extended the claw-free result to the bull-free graphs. It would be, of great interest, at least in our opinion, to understand to what extent forbidding an induced subgraph in a graph impacts the global structure of the graph. In the last few years, people have been studying F-free graphs for different families F, in an attempt to get some insight into this question.

A monumental project in graph theory by Robertson and Seymour was recently completed. This is now called "Graph Minor Theory", and Graph Minors project resulted in many theoretical advances, (e.g. a proof of Wagner's conjecture), but it also has algorithmic applications, and some of the methods have been successfully used in practical computation.

But currently, Graph Minors theory is reasonably understood by many, and several researchers have been working on extensions of Graph minor project. A research program conducted by Jim Geelen, Bert Gerards and Geoff Whittle are extending the results and techniques of the Graph Minor Project of Robertson

and Seymour to matroids. They have already published over 10 papers in Journal of Combinatorial Theory Ser. B (All Graph minor theory papers, except for "Graph Minors II", appeared in Journal of Combinatorial Theory Ser. B). So this project is really "tour de force".

In this workshop, we shall focus on the following two points: extensions of Graph Minor Theory, and applications of Graph Minor Theory techniques and tools. At this moment, we are considering the following topics.

1. Extending to Matrices and Matroid.

As we point out above, Jim Geelen, Bert Gerards and Geoff Whittle are extending the results and techniques of the Graph Minor Project of Robertson and Seymour to matrices and matroids. They have already come up with Graph Minor X for matrices and matroids. We are expecting that they will make progress in the coming few years, and hope that they present their work at the workshop.

2. Digraph Minors and directed tree-width.

Graph minors on undirected graphs are reasonably understood right now, but graph minors on directed graphs are not. For instance, which edges are allowed to contract? There are other fundamental questions in directed graphs.

Directed tree-width is defined by Johnson, Robertson, Seymour and Thomas. This is analogue of tree-width in undirected graphs, but still remains many open questions. One of the fundamental open questions is the following.

In undirected graphs, it is well-known that there is a function $f(r)$ such that every graph with tree-width at least $f(r)$ contains a $r times r$-grid minor. But what about digraphs case? Is there any analogue?

3. Graph Width problem.

Branch-width, Clique-width and Rank-width are attacted attention by many researchers. These invariants are generalizations of tree-width defined by Robertson-Seymour. We would like to report recent advance on this topic.

4. Algorithmic Graph Minor theory

The decomposition theorem capturing the structure of all graphs excluding a fixed minor allows us a lot of algorithmic applications. Many people have worked on many NP-hard problems in minor-closed family of graphs, and they obtained PTAS for these problems. These are generalizations of corresponding results for planar graphs by Baker. Are there any further applications? We would like to report the current status of this direction.

5. Graphs on a fixed surfaces

The family of all graphs which can be embedded on a fixed surface is closed under taking minors. Most of known results about such graphs are summarized in the monograph Graphs on Surfaces by B. Mohar and C. Thomassen. It became apparent that many of these results carry over to general minor-closed families. And conversely, graph minors results imply strong properties for graphs on surfaces.

Perfect graphs include many important families of graphs, and serve to unify results relating colorings and clique problems in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time (Grotschel, Lovasz and Schrijver 1988). In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs.

Berge conjectured that a graph is perfect if an only if no induced subgraph of it is an cycle of odd length at least five (which is called an odd hole), or the complement of one (which is called "odd anti-hole"). Today such graphs are called Berge graphs. The main part of the recent groundbreaking proof of the

Berge conjecture (by Chudnovsky, Robertson, Seymour and Thomas) was a more general theorem that describes the structure of all Berge graphs. More precisely, it was proved that every Berge graph either belongs to one of a few well understood families of basic graphs, or admits a certain decomposition (this was conjectured earlier by Conforti, Cornuejols and Vuskovic). Having obtained this explicit structural result for all Berge graphs, one was able to verify that all of them are perfect. (The other directions of Berge's conjecture is easy, because odd cycles and their complements are not perfect, and every induced subgraph of a perfect graph is). This is now called "The Strong Perfect Graph Theorem".

Recently, Chudnovsky and Seymour have developed the method and techniques used in the proof of Berge' conjecture, and given some fundamental results in this area. However, there are new problems still left in this area. In this workshop, we shall focus on the following problems.

1. Erdos-Hajnal Conjecture

This conjecture claims the following:

For every graph H, there exists a constant t = t(H) > 0, such that if G is an H-free graph, then G contains either a clique or a stable set of size $|V(G)|^t$.

This is concerned with a same kind of the question for perfect graphs, namely whether forbidding a certain induced subgraph has a global effect on a graph.

A recent structural result of Chudnovsky and Seymour allowed to solve a special case of Erdos-Hajnal conjecture, where H is a "bull" graph. The bull graph was one of the smallest subgraph for which the conjecture had not been known, and thus structure theory provided an interesting test case.

2. Building Perfect Graphs

The theorem by Chudnovsky, Robertson Seymour, and Thomas is that every Berge graph either belongs to one of a few well understood families of basic graphs, or admits a certain decomposition (this was conjectured earlier by Conforti, Cornuejols and Vuskovic). Having obtained this explicit structural result for all Berge graphs, one was able to verify that all of them are perfect. But this structure theorem does not tell us how to construct perfect graphs. In particular, one of the ingredients for the decomposition, namely, the skew-partition is a problem, because it may not preserve Berge graphs. So it would be nice if one could get a construction of Berge graphs.

3. Coloring perfect graphs.

The above mentioned result by Grotschel, Lovasz & Schrijver gives rise to a polynomial time algorithm to give an optimal coloring of perfect graphs, but that uses polyhedral method and real numbers. So there should be a "combinatorial" algorithm. This is connected to the second question. Since we do not know how to construct perfect graphs, so, currently, we do not know any combinatorial polynomial time algorithm to find an optimal coloring of a given perfect graph.

4. Recognizing odd holes.

The problem of recognizing Berge graphs is in co-NP (Lovasz 1983), but it was not known whether or not it is in P until after the proof of the Strong Perfect Graph Theorem appeared. (A polynomial time algorithm was discovered by Chudnovsky, Cornuejols, Liu, Seymour, and Vuskovic shortly afterwards, independent of the Strong Perfect Graph Theorem.) Thus one can test whether or not a given graph contains either an odd hole or an anti odd hole in polynomial time. But one major problem in this area is whether or not there is a polynomial time algorithm to recognize an odd hole. This is still open, although there is a polynomial time algorithm to recognize an even-hole (by Chudnovsky, Kawarabayashi and Seymour, and Conforti, Cornuejols, Vuskovic).

5. Construction of F-free graphs.

Recently, Chudnovsky and Seymour managed to give a construction for all claw-free graphs. As in the third question, we do not know how to construct perfect graphs(that is, graphs without odd holes and anti odd holes). Chudnovsky recently extended the claw-free result to the bull-free graphs. It would be, of great interest, at least in our opinion, to understand to what extent forbidding an induced subgraph in a graph impacts the global structure of the graph. In the last few years, people have been studying F-free graphs for different families F, in an attempt to get some insight into this question.

A monumental project in graph theory by Robertson and Seymour was recently completed. This is now called "Graph Minor Theory", and Graph Minors project resulted in many theoretical advances, (e.g. a proof of Wagner's conjecture), but it also has algorithmic applications, and some of the methods have been successfully used in practical computation.

But currently, Graph Minors theory is reasonably understood by many, and several researchers have been working on extensions of Graph minor project. A research program conducted by Jim Geelen, Bert Gerards and Geoff Whittle are extending the results and techniques of the Graph Minor Project of Robertson

and Seymour to matroids. They have already published over 10 papers in Journal of Combinatorial Theory Ser. B (All Graph minor theory papers, except for "Graph Minors II", appeared in Journal of Combinatorial Theory Ser. B). So this project is really "tour de force".

In this workshop, we shall focus on the following two points: extensions of Graph Minor Theory, and applications of Graph Minor Theory techniques and tools. At this moment, we are considering the following topics.

1. Extending to Matrices and Matroid.

As we point out above, Jim Geelen, Bert Gerards and Geoff Whittle are extending the results and techniques of the Graph Minor Project of Robertson and Seymour to matrices and matroids. They have already come up with Graph Minor X for matrices and matroids. We are expecting that they will make progress in the coming few years, and hope that they present their work at the workshop.

2. Digraph Minors and directed tree-width.

Graph minors on undirected graphs are reasonably understood right now, but graph minors on directed graphs are not. For instance, which edges are allowed to contract? There are other fundamental questions in directed graphs.

Directed tree-width is defined by Johnson, Robertson, Seymour and Thomas. This is analogue of tree-width in undirected graphs, but still remains many open questions. One of the fundamental open questions is the following.

In undirected graphs, it is well-known that there is a function $f(r)$ such that every graph with tree-width at least $f(r)$ contains a $r times r$-grid minor. But what about digraphs case? Is there any analogue?

3. Graph Width problem.

Branch-width, Clique-width and Rank-width are attacted attention by many researchers. These invariants are generalizations of tree-width defined by Robertson-Seymour. We would like to report recent advance on this topic.

4. Algorithmic Graph Minor theory

The decomposition theorem capturing the structure of all graphs excluding a fixed minor allows us a lot of algorithmic applications. Many people have worked on many NP-hard problems in minor-closed family of graphs, and they obtained PTAS for these problems. These are generalizations of corresponding results for planar graphs by Baker. Are there any further applications? We would like to report the current status of this direction.

5. Graphs on a fixed surfaces

The family of all graphs which can be embedded on a fixed surface is closed under taking minors. Most of known results about such graphs are summarized in the monograph Graphs on Surfaces by B. Mohar and C. Thomassen. It became apparent that many of these results carry over to general minor-closed families. And conversely, graph minors results imply strong properties for graphs on surfaces.