| Title: | A Short Proof of the Hajnal-Szemeredi Theorem on Equitable Coloring |
| Speaker: | Alexandr V. Kostochka |
| University of Illinois at Urbana-Champaign | |
| Date: | August 29, 2006 |
| Abstract: |
In some applications of coloring as a partition problem one wants color
classes to be not so large or be of approximately the same size. A model
imposing such a requirement is equitable coloring - a proper
coloring where color classes differ in size by at most one. In 1970,
Hajnal and Szemeredi proved that every graph with maximum degree at most r
has an equitable (r+1)-coloring. The proof was surprisingly complicated.
Recently, Mydlarz and Szemeredi found a polynomial time algorithm for such
coloring.
In this talk we give a much simpler proof of the Hajnal-Szemeredi Theorem. It naturally yields another polynomial time algorithm for such coloring. The technique allows us to prove some extensions of the Hajnal-Szemeredi Theorem, but we do not discuss them here. This is joint work with Hal Kierstead. |
| Title: | Lattice polytopes with distinct pair-sums |
| Speaker: | Bruce Reznick |
| University of Illinois at Urbana-Champaign | |
| Date: | September 5, 2006 |
| Abstract: | A lattice polytope P in Rd is the convex hull of a set of points in Zd. Its set of lattice points is P\cap Zd. The polytope has distinct pair-sums if its lattice points {v1,...,vN} have the property that vi + vj = vr + vs implies {i,j} = {r,s}. An example in R2 is the triangle with vertices {(0,0), (2,1), (1,2)} and interior lattice point (1,1). These polytopes have the property that no two differences vi - vj of lattice points point in the same direction; for this reason, they can be called a "box of cats". For such a polytope, we prove that N < 2d and that this is sharp for every d. Open questions include looking for nice constructions. These polytopes have a use in algebraic questions involving sums of squares. |
| Title: | On 2-detour subgraphs of the hypercube / First-fit chromatic number of planar and random graphs |
| Speaker: | Jozsef Balogh / Stephen Hartke |
| University of Illinois at Urbana-Champaign | |
| Date: | September 12, 2006 |
| Abstract: |
A spanning subgraph H of a graph G is a 2-detour
subgraph (or 2-additive spanner) of G if
dH(x,y) < dG(x,y)+2. for all x,y\in
V(G), Studying k-additive spanners was motivated by a number of
problems in communication networks, broadcasting, routing, etc. We prove a
conjecture of Erdos, Hamburger, Pippert, and Weakley by showing that
for some positive constant c and every n, each
2-detour subgraph of the n-dimensional hypercube
Qn has at least clog n\cdot 2n
edges. This is joint work with A. Kostochka. |
| Abstract: | The First-Fit chromatic number of a graph is the maximum number of colors that$ proper coloring may use. We prove various results about the First-Fit chromatic number of outerplanar and planar graphs, random graphs, and Cartesian products of graphs. Specifically, we give asymptotically tight results for outerplanar and random graphs. This is joint work with J. Balogh, Q. Liu, and G. Yu. |
| Title: | List-coloring the square of a subcubic planar graph |
| Speaker: | Daniel Cranston |
| University of Illinois at Urbana-Champaign | |
| Date: | September 19, 2006 |
| Abstract: |
The square G2 of a graph G has the same
vertex set as G, and two vertices are adjacent in
G2 if their distance in G is at most 2. A graph
is subcubic if its maximum degree is at most 3. Dvorak et al.
showed that the list chromatic number
χl(G2) is at most 6 when G is a
planar subcubic graph with girth at least 10. We lower the girth
requirement to 9. We also show that χl(G2)
< 7 when G is a planar subcubic graph with girth at least 7. Both
proofs use discharging. As a result, both proofs lead to easy linear-time
algorithms for constructing the list-colorings.
This is joint work with Seog-Jin Kim (of Konkuk University, Korea). |
| Title: | Degree-splittability for regular graphs |
| Speaker: | Lale Ozkahya |
| University of Illinois at Urbana-Champaign | |
| Date: | September 26, 2006 |
| Abstract: |
A graph G with an even number of edges is degree-splittable
if G decomposes into two graphs with identical degree lists. We
extend the concept to graphs with an odd number of edges by requiring a
decomposition into two graphs with degree lists that are identical except
that two of the degrees in one subgraph are one less than the
corresponding terms in the degree list of the other subgraph.
In this talk we show that every 3-regular graph is degree-splittable using degrees 1 and 2 only. This result implies also (after some additional work) that a 5-regular graph having a 2-factor is degree-splittable using degrees 2 and 3 only. This is joint work with Jeong Ok Choi and Douglas B. West. |
| Title: | Crossing Numbers of Graphs in Surfaces |
| Speaker: | Gelasio Salazar |
| Universidad Autonoma de San Luis Postosi, Mexico | |
| Date: | October 3, 2006 |
| Abstract: | We are often interested in drawing graphs that are nonplanar, that is, that cannot be drawn in the plane without crossings of edges. The minimum number of crossings in a drawing of a graph G in the plane is the ("usual") crossing number cr(G) of G. This gets extended to any surface Σ by defining cr_Σ(G) to be the minimum number of crossings of edges of G in a drawing of G in Σ. In this talk we will survey some of the (few) nontrivial results known about crossing numbers of graphs in nonplanar surfaces. We will also talk about the planar crossing number of graphs that embed in a fixed surface. |
| Title: | The overlap number of a graph |
| Speaker: | Douglas B. West |
| University of Illinois at Urbana-Champaign | |
| Date: | October 10, 2006 |
| Abstract: |
An overlap representation of a graph G is an assignment of
sets to the vertices so that vertices are adjacent if and only if their
assigned sets intersect with neither containing the other. The overlap
number φ(G) (introduced by Rosgen) is the minimum size of
the union of the sets in an overlap representation. We describe the
following results: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the "skeleton" obtained by keeping one leaf incident to each non-leaf vertex that has only one non-leaf neighbor and deleting from the tree all other leaves. (2) The maximum of φ(G) over n-vertex planar graphs is 2n-5 (for n >= 5), achieved by any plane n-vertex graph where every face has length 4 and there is no star-cutset. (3) The maximum of φ(G) over n-vertex graphs is n2/4-n/2-1 (for sufficiently large even n), achieved by the graph obtained by deleting a perfect matching from Kn/2,n/2. |
| Title: | Diameter games on graphs |
| Speaker: | Jozsef Balogh |
| University of Illinois at Urbana-Champaign | |
| Date: | October 17, 2006 |
| Abstract: |
A large class of the so-called Positional Games are defined on the
complete graph on n vertices. The players, Maker and Breaker, take
the edges of the graph in turns, and Maker wins iff his subgraph has a
given -- usually monotone -- property. Here we introduce the
d-diameter game, which means that Maker wins iff the diameter of
his subgraph is at most d. We investigate the biased version of the
game; i.e., when the players may take more than one, and not necessarily
the same number of edges, in a turn. The 2-diameter game has the
(easy) property that Breaker wins the game in which each player chooses
one edge per turn, however it was not known who the winner is when both
players choose two edges per turn. We answer this question.
In addition, we investigate d-diameter games for d>2. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case. (Joint work with Andras Pluhar and Ryan Martin.) |
| Title: | A lower bound on the coupled domination number of n-vertex trees |
| Speaker: | Burak Y. Stodolsky |
| University of Illinois at Urbana-Champaign | |
| Date: | October 24, 2006 |
| Abstract: | Seo and Slater introduced the notion of coupled domination. In their paper they explored how large the coupled domination number γcpl(G) has to be in paths, trees and cycles. They showed that there is a tree T with γ(T)=5 and γcpl(T)=8. This ratio 8/5 is the smallest they found. In this paper we show that γcpl(T)/γ(T)> 1.5 for every tree T except the tree on a single vertex. |
| Title: | A new construction of highly symmetric graphs |
| Speaker: | Aaron Hill |
| University of Illinois at Urbana-Champaign | |
| Date: | October 31, 2006 |
| Abstract: | Does there exist a regular graph that is edge-transitive but not vertex transitive (i.e. semi-symmetric)? Surprisingly (perhaps) the answer is yes. In this talk we review some definitions, give some examples, describe a general construction, and give conditions for when the construction is symmetric, semi-symmetric, and half-transitive. This should be accessible to those who are not familiar with highly symmetric graphs. |
| Title: | Coloring paths in trees |
| Speaker: | Chandra Chekuri |
| University of Illinois at Urbana-Champaign | |
| Date: | November 7, 2006 |
| Abstract: |
We consider the following path coloring problem. Let T be a tree
with integer edge capacities; u(e) denotes the capacity of edge
e. Let P be a collection of paths in T such that the
number of paths that contain an edge e is at most k u(e). We
wish to color the paths in P with ck colors such that the
following property holds: if Pi is the set of paths of
color i then for each edge e of T, the number of
paths in Pi that contain e is at most
u(e). We show that c=4 is sufficient. This problem
generalizes edge coloring in multigraphs (when T is a star) and
hence c > 3/2. Shannon's bound of (3/2) k for edge
coloring
multi-graphs of maximum degree k can be extended to path coloring
on trees when all edge capacities are uniform (that is u(e) = u for
all e). The non-uniform case seems to be more difficult.
This coloring problem is motivated by two problems in routing. Time permitting we will explain the context. This work is a few years old and the goal of the speaker is to interest the audience in resolving the gap between the upper and lower bounds. (Joint work with M. Mydlarz and F. B. Shepherd.) |
| Title: | Short Reports from MIGHTY XLIII |
| Speaker: | Various Graduate Students |
| University of Illinois at Urbana-Champaign | |
| Date: | November 14, 2006 |
| Abstract: | The students will make short presentations about the talks given at the MIdwest GrapH TheorY meeting in Fort Wayne on November 4, 2006. |
| Title: | Divisibility by 3 of the Number of Matchings of a Family of Graphs Convex Subsets of Zk |
| Speaker: | Naeem Sheikh |
| University of Illinois at Urbana-Champaign | |
| Date: | November 28, 2006 |
| Abstract: |
Talk 1: Propp conjectured that for a certain graph obtained by adding extra vertices and edges to the triangular lattice graph, the number of (perfect) matchings is divisible by 3. We will
show that in fact 3(n+1)/2 divides the number of matchings of Gn, where n is the parameter of the family. This is joint work with Stephen Hartke
and Kyung-won Hwang. If time permits, I will also show a slight improvement obtained recently.
Talk 2: Graham, Simonovits and Sós posed the following question in 1980. Let S be a convex subset of Zk, and let Ai be subsets of S such that the intersection of any two of them is non-empty and convex. If the Ai's constitute a maximum such family, is it true that they have a common point? We answer the question in the negative whenever k>1. This is joint work with Kyung-Won Hwang. |
| Title: | On directed triangles in digraphs |
| Speaker: | Alexandr V. Kostochka |
| University of Illinois at Urbana-Champaign | |
| Date: | December 5, 2006 |
| Abstract: |
Using a recent result of Chudnovsky, Seymour, and Sullivan, we slightly improve two bounds related to the Caccetta-Haggkvist Conjecture. We show that if α>
0.35312, then
each n-vertex digraph D with minimum outdegree at least α n has a directed 3-cycle. If β > 0.34564, then every n-vertex
digraph
D where both the outdegree and the indegree of each vertex is at least β n has a directed 3-cycle. This improves the restrictions α >
3-71/2=
0.354248 and β > 0.347785 proved by Shen.
This is joint work with P. Hamburger and P.E. Haxell. |