This bound can be improved for some classes. Chen, Lih, and Wu conjectured that X(G) < \Delta(G) for every connected graph G except complete graphs, odd cycles, and complete bipartite graphs with part-sizes that are equal and odd. They proved this for graphs with maximum degree 3. The conjecture is also proved for bipartite graphs, interval graphs, 2-degenerate graphs, and some other families. The aim of this talk is to prove the Chen-Lih-Wu Conjecture for graphs with low average degree. Given D > 36, we show that X(G) < D for every graph G with maximum degree D and average degree at most D/6 that does not contain a (D+1)-clique.

This is joint work with A.V. Kostochka.

Let G be a connected graph with maximum degree k (other than a complete graph or odd cycle), let W be a precolored set of vertices in G inducing a subgraph F, and let D be the minimum distance in G between components of F. If the components of F are complete graphs and D > 8 (for k > 4) or D > 10 (for k=3), then every proper k-coloring of F extends to a proper k-coloring of G. If the components of F are single vertices and D> 8, and the vertices outside W are assigned color lists of size k, then every k-coloring of F extends to a proper coloring of G with the color on each vertex chosen from its list. The distance thresholds in these results are best possible.

The results are joint work with Michael Albertson and Alexandr Kostochka.

Fundamental problems and results on packing of graphs were given about 25 years ago in papers by Bollobás and Eldridge and by Sauer and Spencer. In this talk, we discuss three conjectures of Bollobás and Eldridge. We prove a special case of the main Bollobás-Eldridge Conjecture. In addition, we extend a conjecture and disprove another conjecture from their paper.

This is joint work with B. Bollobás and K. Nakprasit.

We shall present bounds on SAT(k;n) for various ranges of k; in particular, we shall identify a variety of different types of behaviour. In spite of the host of results, the behaviour of SAT(k;n) remains mysterious, and the major conjectures in the area are far from settled.

In addition to this, we shall present a number of results and problems about two loosely related areas: additions of sets in groups and graphs made up of cliques.

We consider the case (p, q, d)=(4, 3, 2). In [KGT], it was proved that every family of convex sets in the plane having the 3,4-property can be pierced by at most 13 points. As a tool in the proof, we proved that special configurations can be pierced by 5 points, where closed convex sets C₁,..,C_n in the plane form a "special configuration" (with respect to a fixed horizontal line Q) if the following conditions hold:
(i) Each C_i intersects Q in a non-empty interval I_i.
(ii) If I_i and I_j are disjoint, then C_i and C_j intersect above Q.
(iii) If I_i, I_j, I_k are pairwise disjoint, then C_i, C_j, C_k have a common point above Q.

For the minimum number of points that suffice to pierce any family with the 3,4-property, we offer $10 for each decrement below 13 and $30 for each increment above 3. For the minimum number of points that suffice to pierce any special configuration, we offer $20 for each decrement below 5. The offers are consistent, since for every family of convex sets having the 3,4-property, there are three points such that the sets not pierced by them can be partitioned into two special families.

[KGT] D. J. Kleitman, A. Gyárfás, G. Toth, Convex sets in the plane with three of any four meeting, Combinatorica 21 (2001) 221-232.

We use a concept called "gap number". For an edge e with endpoints u and v and weight w(e), let gap(e)=d_G-e(u,v)-w(e). For a spanning tree T in a graph G, let gap(G,T) be the maximum over all edge-weightings of G of the sum of the gaps of edges outside T divided by the total weight of T. For a graph G, define the gap number gap(G) to be the maximum of gap(G,T) over all spanning trees T.

We show that a graph with gap number \Omega(r(log r)^1/2log n) has a K_r-minor. We also show that this dependence on n is nearly tight, by exhibiting graphs with no K₆-minor (apex graphs) and gap number \Omega((log n)/loglog n). As a step toward eliminating the log n factors in the first paragraph, we propose a generalized gap number, now depending on \epsilon, and we show that it remains bounded for apex graphs, circular-arc graphs, and some similar graph families.

Let D(n,k) be the minumum positive integer d such that every n-vertex graph with minimum degree at least d is k-linked. Bollobás and Thomason, and Thomas and Wollan used the bound D(n,k)< (n+3k)/2-1 to give sufficient conditions for a graph to be k-linked in terms of connectivity.

Our main result is the exact value of D(n,k) for every n and k. We can further guarantee that when the minimum degree is at least D(n,k), the resulting paths P₁,..., P_k in each linkage can be chosen to visit all vertices of G.

We find also the exact values for the corresponding Ore-type bound: If d(x)+d(y)> 2D(n,k) for all nonadjacent vertices x and y in an n-vertex graph G, then G is k-linked.

Our bound allows us to slightly modify the Thomas-Wollan proof to show that every 2k-connected graph with average degree at least 12k is k-linked. It then follows that every 12k-connected graph is k-linked. This improves the previous result of Thomas and Wollan that every 16k-connected graph is k-linked.

These results are joint work with A. Kostochka.

Here we introduce the concept of \gamma-labeling of an almost-bipartite graph. We show that if an almost-bipartite graph G with n edges has a \gamma-labeling, then there is a cyclic G-decomposition of K_2nx+1 for all positive integers x. We also show that odd cycles as well as certain other almost-bipartite 2-regular graphs have \gamma-labelings.

(Joint work with Saad El-Zanati and Charles Vanden Eynden)

This is joint work with Jeong-Han Kim, Joel Spencer, Helmut Veith, and Oleg Verbitsky. The talk should be accessible to a general mathematical audience.

Classical results on VIP of that kind have been for a long time restricted to just three graph families: hypercubes, grids, and tori. The theory of VIP was essentially the theory of these examples. We present several new infinite graph series. To obtain these results, we have developed and extensively used some software that is interesting on its own. The software allows solving the VIP and some other versions of graph isoperimetric problems for a graph and its second cartesian power, check whether there exist nested solutions, and output one of them. Some experimental results that we discovered for the second power were then generalized to arbitrary power and turned into theorems. In the course of this research we extended some our older results concerning the relationship between VIP and some extremal poset problems. The lecture will include some demonstration of the software.