DREI '98 Graph Theory & Combinatorial Optimization

"Extending Graph Colorings"

Given an r-chromatic graph G and an r-coloring of P C V(G) it is natural to wonder if the coloring of P can be extended to all of G. Read and Wright and Biro, Hujter, and Tuza have considered the complexity of this question. Would using an additional color help? Thomassen posed the following problem: Suppose G is planar and the distance between any two vertices in P is at least 100. Can any 5-coloring of P be extended to a 5-coloring of G? Th. If x(G) = r and the distance between any two vertices in P is at least 4, then any r+ 1coloring of P extends to an r + 1-coloring of all of G. It is known that no recoloring result of this nature can hold. If P consists of disjoint and distant cliques similar results hold. If the components of P are not cliques, then an extension may require additional colors. In some instances (e.g. if the graph is locally planar), then no additional colors are necessary. This talk will introduce this subject, survey some of its highlights, and present a handful of intriguing open questions.

"Perfectly Orderable Graphs and Unique Colorability"

Omitting any vertex of a minimally imperfect graph, we obtain a uniquely colorable perfect one. This is equivalent to Padberg's theorem. So, such graphs can be useful in attacking the Perfect Graph Conjecture. There are many open problems on the combinatorial properties of uniquely colorable perfect graphs, e.g. the so-called Clique-pair Conjecture (Fonlupt-Sebo): If a uniquely colorable perfect graph is not a clique then it contains two maximum cliques with a two-element symmetric difference. This conjecture is proved for many classes of perfect graphs. A graph is perfectly orderable if there exists a complete order less than that of its vertices such that no induced subgraph on vertices a,b,c,d exists with edges ab,bc,cd and a less than b, d less than c. (This configuration can be called obstructing P_4) For perfectly orderable graphs which yield a large subclass of perfect graphs, there are only partial results. We deal mostly with the following one: If G is a perfectly orderable graph and it is a counterexample for the Clique-pair Conjecture, then it contains two adjacent vertices x,y such that all the maximum cliques containing x, contain y.

"Optimal Ear Decompositions of Bricks"

Motivated by his work on the matching lattice, Lovasz conjectured in 1987 that every brick different from K_4, C_6, and the Petersen graph has an edge whose deletion yields a matching covered graph with exactly one brick. In a paper submitted to the Journal of Combinatorial Theory, Series B, we have proved the following theorem.

Theorem 1: Every brick different from K_4 and C_6 and not having the Petersen graph as its underlying simple graph has an edge whose deletion yields a matching covered graph with exactly one brick,with the additional property that the underlying simple graph of that one brick is different from the Petersen graph. Our Theorem, although apparently more general than Lovasz's conjecture, is in fact equivalent to it. Our proof involves establishing an interesting new property of the Petersen graph. As a consequence of Theorem 1, we obtain the following theorem which answers a question raised by Naddef and Pulleyblank.

Theorem 2: If G is any brick whose underlying simple graph is not isomorphic to the Petersen graph, then there is an ear decomposition of G with exactly one double ear. (More generally, for any matching covered graph G, the least number of double ears that an ear decomposition of G may have is b(G)+p(G) where b(G) is the number of bricks of G and p(G) is the number of bricks of G whose underlying simple graphs are isomorphic to the Petersen graph.)

Using Theorem 2, we show that for any matching covered graph G, there is a basis for the matching lattice of G consisting of incidence vectors of perfect matchings of G. This answers a question raised by Murty. We are in the process of finishing a paper which includes the above mentioned applications of Theorem 1.

"Coloring and Independence Ratio of Circulants"

If S is a subset of {1,2,3,...,[n/2]}, let C(n,S) denote the circulant graph on these n vertices with vertices i and j adjacent whenever |i-j| or (n - |i-j|) lies in S (where [x] is the greatest integer less than x). Let m(G) be the independence ratio of G, that is, its independence number divided by its number of vertices. Let N be the sum of the smallest and largest elements of S, and let U(S) be the graph with vertices labeled 1,2,3,...,N such that i is adjacent to j if |i-j| lies in S. We show that m(C(n,S)) is at most m(U(S)). If N - S = S, then the lim m(C(n,S)) = m(S) as n goes to infinity. We conjecture that in this case, m(C(n,S)) = m(S) when n is sufficiently large. We further show that if C(n,S) has odd girth 2k+1, then m(C(n,S)) is at most k/(2k+1). If the vertex degree of C(n,S) is sufficiently large, then we get that m(C(n,S)) = k/(2k+1). We also demonstrate some pretty 4-colorings of C(n,{1,r}) and C(n,{1,r-1,r}), which can be embedded, respectively, as quadrangulations and triangulations of the torus.

"Non-Abelian Flows"

We consider group valued flows on a graph, where the group in question is non-abelian. In order to make this a sensible notion, the graph must be imbedded on a surface. We will state, and briefly sketch a proof giving necessary and sufficient conditions (based on the embedding) for the existence of a nowhere zero flow in some non-abelian groups.

"Characterizing Uniquely 4-Colorable Planar Graphs"

Fiorini and Wilson conjectured in 1977 that a uniquely edge 3-colorable cubic planar graph always contains a triangle. This is equivalent to the statement that every uniquely vertex-4-colorable planar graph has a vertex of degree three and implies that every such graph can be constructed from the complete graph on four vertices by repeatedly adding vertices of degree three. We give a computer assisted proof of this conjecture. More precisely, using the techniques of a recent proof of the Four-Color Theorem, we prove from first principles that every ``internally 6-connected'' planar triangulation has at least two vertex -4-colorings. The Four Color Theorem follows as a corollary. This is joint work with Robin Thomas.

"Co-Coloring Graphs of Fixed Genus"

Given G, a graph, a cocoloring of G is a partition of V(G) where each part induces a complete or empty graph. The cochromatic number, z(G), of G is the minimum order of all cocolorings of G. We show that if G has genus n, then the cochromatic number of G is at most sqrt(n)/log (n)

This bound is sharp. We will see this is related to the problem of finding the maximum chromatic number of all triangle-free graphs of genus n.

"Colouring the Maximal cliques of a graph"

We consider the coloring of the hypergraph H(G) defined by the maximal cliques of a graph G. This problem is known to be NP-complete. We give relations between some parameters of G and x(G) the minimum number of colors needed to color H(G) Motivated by a question mentioned by Jensen and Toft, we study the special case when the graph G is perfect. This question asks whether x(G) is bounded when G is perfect. For example, the hypergraph of a strongly perfect graph is, by definition, 2-colorable. We prove that x(G) = 3 if G is a claw-free perfect graph, or a diamond-free perfect graph without flat edge.'

"Independent Sets in Triangle-Free Cubic Planar Graphs"

Albertson, Bollobas, and Tucker conjectured in 1976 that every triangle-free cubic planar graph on v vertices has an independent set of size at least sv, for some s > 1/3, with s possibly as large as 3/8. In this paper we prove this is so for s = 3/8. This is a joint work with Robin Thomas

"List partitions"

I will discuss complexity questions for list partition problems, which generalize both list colourings and list homomorphisms. These problems include finding homogeneous sets, Chvatal's skew-cross partitions, clique cutsets studied by Whitesides and Tarjan, and Brandstadt's generalizations of split graphs. We give several new polynomial time algorithms and NP-completeness results. In certain other cases we give algorithms which are only slightly superpolynomial. However, we pose many more questions than we answer. This is joint work with T. Feder, S. Klein, and R. Motwani.

" Removing circuits and contracting bonds in graphs, cographs and matroids"

Around 1975, A.M. Hobbs posed the question whether every 2-connected eulerian multigraph G with minimum degree at least four contains a circuit C such that G-E(C) is still 2-connected. A positive answer to this question would imply the Cycle Double Cover Conjecture. But counterexamples by N. Robertson and B. Jackson showed that the answer to this question must be "no" in general. In 1980, B. Jackson proved that the question has a positive answer for simple graphs, and that in fact the requirement that the graph is eulerian is not necessary. Further extensions have been made since then, including a proof for planar multigraphs of the following result by L.A. Goddyn and the speakers: A 2-connected multigraph G with minimum degree at least four and containing no Petersen graph as a minor, contains two edge-disjoint circuits C such that G-E(C) is 2-connected. An obvious question is if and how far the above result can be generalised to matroids. In particular the following question has been the topic of some research: What is the largest (minor-closed) class of matroids such that every connected matroid M in this class having cogirth at least four has a circuit C such that M-C is connected? For cographic matroids, the question above is equivalent to finding a bond (a minimal edge-cut) B in a 2-connected graph with girth at least four, such that the graph resulting after contracting all edges in B is still 2-connected. In the talk we discuss relations between work on removable circuits and related topics such as circuit covers. Another topic we address during the talk is the question about the complexity of finding removable circuits. It appears that, although we know that certain classes of graphs (classes that can be recognised in polynomial time) contain a removable circuit, we don't always know a polynomial time algorithm that will actually find such a circuit. Many open problems in this area remain.

"Reducible configurations for the cycle-double-cover-conjecture "

The well-known CDC conjecture states that each bridgeless graph contains a k-CDC for some integer k, i.e. a system of k cycles covering each edge exactly twice (here a cycle is a subgraph in which each vertex has an even degree). In 1985, Goddyn proved that each circuit of length at most 6 is reducible for the CDC conjecture (i.e. such a circuit cannot be contained in a minimal counterexample) so that each minimal counterexample has girth at least 7. We refine and schematize Goddyn's method so that reducibility of graphs (not necessarily circuits) can be proved just by performing some verification algorithms. By implementing these algorithms on a computer, we can prove so far that each counterexample to the CDC-conjecture has girth at least 12. Moreover, each counterexample to the 5-CDC-conjecture (each bridgeless graph has a 5-CDC) has girth at least 10. Finally, based on a result of Robertson, Seymour, and Thomas, we can verify the 5-CDC-conjecture for all bridgeless cubic graphs without the Petersen graphs as a minor and we present an approach to the non-cubic case.

"On four-coloring even triangulations"

Heawood's theorem (also observed by Kempe) states that a planar triangulation can be 3-colored if and only if all vertices have even degree. With K. Collins we have conjectured that an even triangulation on an orientable surface of positive genus can be 4-colored provided the edge-width is sufficiently large. We report on progress on solving this conjecture for the torus. The analogous 4-coloring conjecture for the projective plane is false, as shown with B. Richter. This talk includes joint work with M. Albertson, K. Collins, D. Fisher, B. Richter, and P. Seymour.

"On(a,w)graphs"

We study the Laplacian spectrum of (a,w)--graphs. The properties of the spectrum we found allow to establish some strucural properties of (a,w)--graphs. We describe in particular a class of graphs that are not subgraphs of (a,w)--graphs.

"Superposition and constructions of graphs without nowhere-zero k-flows"

We deal with a systematical approach for constructions of graphs without nowhere-zero k-flows. The main tool we introduce is superposition, a very powerful method which ideas we have already used by constructions of special classes of snarks (nontrivial 3-regular graphs without 3-edge-coloring, or equivalently, without nowhere-zero 4-flows). We also present other methods which generalize and bring together almost all constructions of snarks known until now. As a byproduct of our theories we obtain some new results about nowhere-zero flows.

"The choice number of random bipartite graphs"

The choice number ch(G) of a graph G is the minimum integer k such that for every assignment of a list S(v) of k colors to every vertex v of G (lists for different vertices may be different), there is a proper coloring of G that assigns to each vertex v a color from S(v). The concept of the choice number was introduced by Vizing in 1976 and independently by Erdos, Rubin and Taylor in 1979. Although it is a straightforward generalization of the chromatic number of a graph, the choice number appears to be a much more complicated parameter and much less is known about it. We will discuss the problem of determining the asymptotic behavior of the choice number of random bipartite graphs. This question has already been addressed in the original paper of Erdos, Rubin and Taylor. The random bipartite model G(n,n,p) is a probability space, whose elements are labeled bipartite graphs with vertex classes A and B, both of size n, where a vertex from A and that from B are connected by an edge randomly and independently with probability p=p(n). Our main result states that for all C/n less than p(n)less than 9/10, the choice number of the random bipartite graph G(n,n,p) is asymptotically equal to log_2(np). The proof relies on expansion properties of random bipartite graphs and a connection between choosability in bipartite graphs and a well known problem of Erdos about minimal possible number of edges in a non-2-colorable n-uniform hypergraph, exposed already in the paper of Erdos, Rubin and Taylor. This is a joint work with Noga Alon, Tel Aviv University, Israel.

"Upper Chromatic Number of Steiner Systems"

In a mixed hypergraph, two types of sets are distinguished, namely the edges and the antiedges (both are subsets of the vertex set). In a colouring of a mixed hypergraph, every anti-edge has at least two vertices of the same colour and every edge has at least two vertices coloured differently. The upper chromatic number, denoted X, is the maximum number of colours that can occur in a colouring. The concepts of mixed hypergraph and upper chromatic number are applied to Steiner Triple and Quadruple Systems and S(2, 4, v). We consider a Steiner system as a mixed hypergraph where either all blocks are anti-edges (denoted CSTS and CSQS, named after the term "co-hypergraph") or all blocks are edges and anti-edges at the same time (BSTS and BSQS). Necessary conditions for the existence of a colouring in a BSTS, CSTS and BSQS, CSQS are given. It is proved that a CSTS or a BSTS of order v < 2k - 1 has upper chromatic number at most k, and that this bound is the best possible. The exact value of X for three infinite classes of BSTS and CSTS is determined and a lower bound of X for an infinite class of CS(2, 4, v) is found. For particular CSQS of order v = 2k, one can show that X > k + 1 and that the cardinality of each colour class is greater than or equal to 2 if X > k+ 1. As regards systems of small orders, the exact value of X is determined for BSQS(8), CSQS(8), BSQS(1O), CSQS(10), BSQS(16), CSQS(16), CSQS(32). A new parameter is also introduced: the monochromatic block number mb, defined as the number of monochromatic blocks in a colouring of a mixed hypergraph. A formula for the exact value of mb is given for every colouring in CSTS(v), in terms of the cardinalities of the colour classes. Moreover, in particular CSQSs, upper and lower bounds for mb are found.

"Variations of the Classical Ramsey Problem"

A coloring of the edges of K_n is constructed such that every copy of K_4 has at least three colors on its edges. As n tends to infinity, the number of colors used is e^sqrt{log n}. This radically improves upon the previous (probabilistic) bound of (sqrt n ) due to Erdos and Gyarfas. We also consider a bipartite version of this problem.

"Coloring of Colored and Mixed Structures"

We survey recent results related to homomorphisms and colorings of graphs and relational structures. We illustrate some unifying features (such as density and duality; joint work with C.Tardif) aswell as differencies. In this framework we discuss restricted colorings (joint work with A.Raspaud) and OPPDC and CDC problems (joint work with J.Maxova).

"Flows and Antiflows, Colorings and Strong Colorings of Oriented Graphs"(G)"

The homomorphisms of oriented or unoriented graphs, the oriented chromatic number, the relationship between acyclic coloring number and oriented chromatic number, have been recently intensely studied. For the purpose of duality, we define the notions of strong oriented colouring and antiflow. An antiflow is a flow with values in an additive abelian group which use no opposite elements of the group. We prove that the strong oriented chromatic number Xs (as the modulo version of oriented chromatic number) is bounded for planar graphs. By duality we obtain that any oriented planar planar graph has a Z{5}times Z{6})^{5\2}-antiflow. Moreover we prove that any 3-edge connected oriented graph G has an antiflow with values in a group whose order depends only of the dimension of the cycle space of the graph G. We list open problems analogous to those for nowhere-zero flows.

"Graph Colouring via the probabilistic method"

We overview a plethora of recent results on graph colouring obtained using the probabilistic method, in particular the Lovasz Local Lemma combined with concentration inequalities. The talk is intended to be a gentle introduction to the techniques in the area and is aimed at a general audience.

"The Four-Colour Theorem"

The four-colour problem was an open question for 125 years, and became one of the most famous problems in all of mathematics, until its solution by Appel and Haken in 1977. Much of modern graph theory grew from attempts to solve it, and it can reasonably be called the most important theorem in graph theory. This talk will be a survey, at an elementary level, of aspects of the four-colour theorem, including a sketch of its proof.

"Flows, Coloring and 19th Century's Invariant Theory"

"Tutte's edge 3-coloring conjecture"

Tutte conjectured in 1966 that every 2-connected cubic graph with no minor isomorphic to the Petersen graph is edge 3-colorable. The conjecture implies the Four Color Theorem by a result of Tait. In the first part of the lecture I will discuss related results and problems. In the second part I will outline a proof of Tutte's conjecture obtained in joint work with N. Robertson, D.P. Sanders and P.D. Seyour.

"Timetables, Factors and Colorings"

Suppose we wish to schedule parent-teacher interviews at a local school. Each parent/couple of parents decide beforehand on a list of teachers that he/she/they would like to talk to. Each interview is supposed to take the same fixed amount of time. The problem is to arrange a schedule in such a way that there will be no waiting periods for neither parents nor teachers, or as few as possible. Even for some simple situations the answer to this problem is unknown, for example it is not known if waiting periods can be avoided in the case where each parent wants to meet exactly 3 teachers and each teacher is demanded by exactly 4 parents. The talk will discuss this time tabling problem in terms of graph edge- colorings. Even if the topic at first sight may seem rather special and restricted, it turns out to have strong relations to classical topics in combinatorial mathematics and graph theory, like finite planes and factorization of graphs. Some of the subproblems that emerge are exactly the same as those first studied by James Joseph Sylvester and Julius Petersen in 1889. Thus there are also strong links to the history of graph theory. The lecture will take up these historical aspects and show how results that we today consider simple and easy were not at all simple and easy when they were first encountered - not even for great minds like Sylvester and Petersen. The story is an interesting piece of mathematics history, involving also Cayley, Hilbert and Klein.

"Coloring of mixed hypergraphs: results and open problems"

A mixed hypergraph H = (X, C, D) consists of the vertex set X, family of C-edges C and family of D-edges D. In every proper coloring, each C-edge has at least two vertices of Common color, and each D-edge has at least two vertices of Different colors. The largest [smallest] number of colors for which there exists a coloring using that many colors is called the upper [lower] chromatic number of X, denoted by x(X) [x(X)]. Mixed hypergraph is called: a) uncolorable if it admits no coloring; b) uniquely colorable if it admits exactly one coloring apart from permutation of colors; c) C-perfect if for each induced subhypergraph the upper chromatic num ber equals the maximum size of a vertex subset containing no C-edges; d) pseudo-chordal if it can be decomposed by consecutive elimination of simplicial vertices, where a vertex is simplicial if its neighborhood induces a uniquely colorable subhypergraph. We survey the results and open problems on colorability, unique col orability, C-perfection, algorithmic aspects of upper chromatic number, and possible applications. In particular, we discuss analogues of the Berge Perfect Graph Conjecture, the four color problem, and the problem of chromatic index of graphs.

"3-Coloring the Klein Bottle"

We prove that every graph on the Klein Bottle which does not contain contractible cycles of length 3 or 4 is either 3-colorable or has a subgraph isomorphic to a member of a particular family of non-3-colorable graphs. Every member of this family has triangles, and hence graphs on the Klein Bottle without quadrilaterals or triangles are 3-colorable. This solves a problem raised by Woodburn in 1989.

"Constrained Colouring -- The radio channel assignment project"

A typical version of the radio channel assignment problem can be described as follows. Given a planar graph G, consider its vertices as radio transmitters. The problem is to find an assignment ~ of frequencies (= colours) to the vertices of G which obeys the following rules:

Given a set of integers kit, k2, ..., kr if the distance between $ and y is j < r, then the colours ¢(~) and ¢(y) assigned to vertices a, y must satisfy1¢~(27) - ¢(Y) > kj. The chromatic number of such a problem is the minimum number of colours needed in such an assignment. The case kit = 1, k2 = k3 = . . . = kr = O corresponds to ordinary graph colouring. This problem is of huge commercial interest. However, exact results are scarce. I shall attempt to give a survey of what is currently known and describe some of the open problems of a combinatorial or algorithmic nature that I find particularly appealing.

" Covering Designs and Domination in Kneser Graphs (joint work with Christopher M. Hartman)"

The covering number C(n,l,k) is the minimum size of a family F of l-subsets of an n-set such that every k-set is contained in (covered by) some l-set in F. We determine C(n,n-r,k) for n(3/4)rk+r; the value is k+1+\lceil\frac{r(k+1)-n}{floor r/2 floor}ceil. The Kneser graph K(n,k) is the graph of the disjointness relation on the k-element subsets of an n-set. When r=k, the covering number C(n,n-r,k) equals the total domination number of K(n,k). When n(3/4)k^2+k, we prove that the domination number gamma(K(n,k)) also has the value C(n,n-k,k) given above.

"Hamilton weights and critically non-faithful coverable graphs"

A (1, 2)-eulerian weight w of a cubic graph is called a Hamilton weight if every faithful circuit cover of the graph with respect to w is a set of two Hamilton circuits. Let G be a 3-connected cubic graph containing no Petersen minor. It is proved that G admits a Hamilton weight if and only if G can be obtained from K_4 by a series of delta-Y operations. With a similar argument, it is also proved that if G is a permutation graph and w is a (1,2)-eulerian weight of G such that (G,w) is a critical contra pair, then the Petersen minor appears `almost everywhere' in the graph G. (Joint work with H. J. Lai)

"Coloring Edges of Graphs Embedded in Surfaces"

In this talk, we will talk about some conditions which guarantee graphs embedded in some surfaces to be class one.

"Circular Chromatic Number of Graphs"