| Title: | Domination in cubic hamiltonian graphs / Domination in connected cubic graphs |
| Speaker: | Alexandr V. Kostochka / Burak Y. Stodolsky |
| University of Illinois at Urbana-Champaign | |
| Date: | August 30, 2005 |
| Abstract: |
Part 1: The domination number of a graph G is the
minimum size of a set S such that every vertex outside S has
a neighbor in S. A graph is cubic if every vertex has
degree 3 and Hamiltonian if it has a cycle through all the
vertices. The domination number of an n-vertex Hamiltonian graph
is clearly at most the ceiling of n/3.
Plummer suggested that "ceiling" can be improved to "floor" for every
cubic n-vertex hamiltonian graph with n>8. This is
obviously true whenever n is divisible by 6. We prove that the
conjecture is true whenever n is congruent to 4 modulo 6 and false
whenever n is congruent to 2 modulo 6. This is joint work with M.
Cropper, D. Greenwell, and A.J.W. Hilton. Part 2: In 1996, Reed proved that the domination number of every n-vertex graph with minimum degree at least 3 is at most 3n/8. Also, he conjectured that the upper bound improves to the ceiling of n/3 for every connected 3-regular n-vertex graph G. We disprove this conjecture. We construct a connected cubic graph on 60 vertices with domination number 21 and a sequence of connected cubic graphs where the limit of the ratio of the domination number to the number of vertices is at least 8/23, which equals 1/3+1/69. This is joint work with A. Kostochka. |
| Title: | On the power of linear dependences |
| Speaker: | Imre Bárány |
| Rényi Institute, Budapest, and University College, London, UK | |
| Date: | September 6, 2005 |
| Abstract: | Starting with an old result, the so-called ``Vector-sum Theorem'', we explain how linear algebra can help solve various geometric and combinatorial problems. Several examples will illustrate the power of this technique. |
| Title: | Graph classes characterized by both forbidden induced subgraphs and degree sequences |
| Speaker: | Michael Barrus |
| University of Illinois at Urbana-Champaign | |
| Date: | September 13, 2005 |
| Abstract: | Given a family F of graphs, a graph G is F-free if G does not contain any member of F as an induced subgraph. We say that a family F is potential-forcible if, for each graph G in the class C of F-free graphs, every realization of the degree sequence of G is also in C. For instance, {2K2,C4,C5} is a potential-forcible family that defines the split graphs. In this talk we will consider what families of graphs are potential-forcible, including a complete characterization when F has at most two graphs. |
| Title: | Bar k-visibility graphs |
| Speaker: | Jennifer Vandenbussche and Paul Wenger |
| University of Illinois at Urbana-Champaign | |
| Date: | September 20, 2005 |
| Abstract: | A bar visibility representation of a graph G is a collection of horizontal bars in the plane corresponding to the vertices of G such that two vertices are adjacent if and only if the corresponding bars can see each other along an unobstructed vertical sightline. In a bar k-visibility graph, a bar can see another bar if there are at most k intervening bars along a vertical sightline. We present several results about bar k-visibility graphs, including a sharp upper bound on the largest size of a complete bar k-visibility graph, forbidden induced subgraphs, and regular bar k-visibility graphs. This is joint work with Stephen Hartke. |
| Title: | Distingushing chromatic number of cartesian products of graphs |
| Speaker: | Jeong Ok Choi |
| University of Illinois at Urbana-Champaign | |
| Date: | September 27, 2005 |
| Abstract: | A k-coloring of the vertices of a graph G is a proper distinguishing coloring if (1) the coloring is proper (adjacent vertices get different colors), and (2) the only coloring-preserving automorphism of G is trivial. Thus a proper distinguishing coloring is a proper coloring that breaks all symmetries of the graph. The distinguishing chromatic number of a graph G is the minimum k such that G has a proper distinguishing k-coloring. The chromatic number is an obvious lower bound; we prove that for sufficiently large cartesian powers of graphs only one additional color is needed. In particular, we find the distinguishing chromatic number for hypercubes, cartesian products of complete graphs (Hamming graphs), and cartesian products of complete multipartite graphs. This is joint work with Stephen Hartke and Hemanshu Kaul. |
| Title: | Edge-bandwidth of graphs |
| Speaker: | Jozsef Balogh |
| University of Illinois at Urbana-Champaign | |
| Date: | October 4, 2005 |
| Abstract: | An edge-labeling of a graph G is a bijection from E(G) and 1,...,|E(G)|. The bandwidth of a labeling h is max |h(e)-h(f)|, where the maximum is taken over all pairs of adjacent edges. The edge-bandwidth of a graph G is the minimum bandwidth among all edge-labelings. We asymptotically determine the edge-bandwidth of several "grid"-type graphs (that is, cartesian products): Pn*Pn, Cn*Cn, Kn*Kn and K2n. Here Pn, Cn, Kn are the path, cycle, and complete graph with n vertices, respectively, and K2n is the n-dimensional hypercube. This is joint work with Dhruv Mubayi and András Pluhár. |
| Title: | The induced Turán problem for forbidden induced paths |
| Speaker: | Doug West |
| University of Illinois at Urbana-Champaign | |
| Date: | October 11, 2005 |
| Abstract: | A graph is H-free if it has no induced subgraph isomorphic to H. Let f(D;H) be the maximum number of edges in an H-free connected graph with maximum degree D; this is finite if and only if H is a disjoint union of paths. Earlier results include f(D;P4)=D2 and the exact computation of f(D;2P2) and f(D;2P3). We determine f(D;Pm) asympotically for m > 6 and f(D;P5) exactly for large D. For m > 6, we have f(D;Pm) ~ (1/2) Dm/2 when m is even and f(D;Pm) ~ (1/8) D(m+1)/2 when m is odd. These results also give good bounds for f(D;H) when H consists of t components isomorphic to Pm. (This is joint work with Myung S. Chung and Tao Jiang.) |
| Title: | The Distinguishing Number of the Iterated Line Graph / 2-Factors in Iterated Line Graphs |
| Speaker: | Ian Shipman / Stephen Hartke |
| University of Illinois at Urbana-Champaign | |
| Date: | October 18, 2005 |
| Abstract: |
Part 1:
The line graph L(G) of a simple graph G is the graph whose
vertices are the edges of G, adjacent in L(G) if they have a
common endpoint in G. We iterate the line graph by setting
Lk(G) = L( Lk-1(G) ). A graph G is
distinguished by k colors if has a vertex coloring such that there
are no non-trivial color-preserving automorphisms.
We show that for every simple graph G other than the cycles
C3, C4, C5 and the claw
K1,3, there exists K > 0 such that for k >
K the kth iterate Lk(G) can be distinguished
by two colors. Additionally, the distinguishing number d(G) of a
graph G is the minimum k such that G is distinguished
by k colors; we determine those trees T such that
d(L(T))>d(T).
Part 2: Despite being very sparse, when k is large the iterated line graph Lk(G) has very nice connectivity properties. For instance, it is hamiltonian. We show that when k is sufficiently large, Lk(G) has the stronger property of being 2-factor spectrum complete: if 1 < j < n(Lk(G))/3, then Lk(G) has a 2-factor with exactly j cycles. We also develop some conditions that permit specifying the lengths of the cycles in the 2-factor. This is joint work with Mike Ferrara of the University of Colorado at Denver and Ron Gould of Emory University. |
| Title: | Inequalities for the First-Fit chromatic number |
| Speaker: | Zoltán Füredi |
| University of Illinois at Urbana-Champaign | |
| Date: | October 25, 2005 |
| Abstract: |
The First-fit (or Grundy) chromatic number of G, written as
\chi_{FF}(G), is defined as the maximum number of classes in an
ordered partition of V(G) into independent sets so that each vertex
has a neighbor in each set earlier than its own.
The well-known Nordhaus-Gaddum Inequality states that the sum of the ordinary chromatic numbers of an n-vertex graph and its complement is at most n+1. M. Zaker suggested finding the analogous inequality for the First-fit chromatic number. We show that the floor of (5n+3)/4 is an upper bound, and this is sharp when n=4k>4. We extend the problem for multicolorings as well. We also show that the smallest order of C4-free bipartite graphs with \chi_{FF}(G)=k is asymptotically 2k2 (the upper bound answers a problem of Zaker). This is joint work with Gyárfás, Sárközy, and Selkow. |
| Title: | On a graph packing conjecture |
| Speaker: | Gexin Yu |
| University of Illinois at Urbana-Champaign | |
| Date: | November 1, 2005 |
| Abstract: |
Two n-vertex graphs G1 and G2
pack if G1 and G2 can be
expressed as edge-disjoint subgraphs of Kn. Special
cases of the problem of whether two given graphs pack include problems on
existence of fixed subgraphs, on forbidden subgraphs, and on equitable
coloring. Graph packing has also been applied in studying computational
complexity of graph properties. Let \Delta(G) denote the maximum
degree of a vertex in G.
Bollobás and Eldridge (also Catlin, independently) conjectured that if |V(G1)|=|V(G2)|=n and (\Delta(G1)+1)(\Delta(G2)+1) < n+1, then G1 and G2 pack. If true, this conjecture would be sharp, and it would be a considerable extension of the Hájnal-Szemerédi theorem on equitable coloring. The conjecture has only been proved in cases where G1 is highly degenerate, or \Delta1 < 2, or \Delta1=3 and n is huge. In this talk, we take a different approach to the conjecture. Given n-vertex graphs G1 and G2, we prove that if \Delta(G1), \Delta(G2) > 400 and (\Delta(G1)+1)(\Delta(G2)+1) < 0.6n+1, then G1 and G2 pack. This is joint work with H. Kaul and A. Kostochka. |
| Title: | On Ramsey numbers for sparse uniform hypergraphs |
| Speaker: | Alexandr Kostochka |
| University of Illinois at Urbana-Champaign | |
| Date: | November 8, 2005 |
| Abstract: |
For a k-uniform hypergraph G, the Ramsey number
R(G,G) is the least N such that in every 2-coloring of edges
of a complete n-vertex k-uniform hypergraph, there is a
monochromatic copy of G. A family F of k-uniform
hypergraphs is f(n)-Ramsey if there is a positive constant
c such that R(G,G) < c f(|V(G)|) for every G\in
F.
Burr and Erdös conjectured that for every d, the families M(d) of graphs with maximum degree d and D(d) of d-degenerate graphs are n-Ramsey. Recall that a graph is d-degenerate if each subgraph has a vertex of degree at most d. Chvátal, Rödl, Szemerédi and Trotter proved the first conjecture. The second is open. However, Kostochka and Rödl proved that D(d) is n2-Ramsey, and then Kostochka and Sudakov proved that the family is n1+\epsilon-Ramsey for every positive \epsilon. In this talk, we prove that for every \epsilon > 0 and every k and d, the family D(d,k) of k-uniform hypergraphs with maximum degree at most d is n1+\epsilon-Ramsey. We also give some examples showing that the graph and hypergraph cases behave differently. This is joint work with V. Rödl. |
| Title: | Edge-choosability of planar graphs with no adjacent triangles |
| Speaker: | Daniel Cranston |
| University of Illinois at Urbana-Champaign | |
| Date: | November 15, 2005 |
| Abstract: |
Vizing conjectured that every graph G is
(\Delta(G)+1)-edge-choosable, where \Delta(G) denotes the
maximum vertex degree of G; this would strengthen Vizing's Theorem
that G is (\Delta(G)+1)-edge-colorable. For planar graphs,
this has been proved for \Delta(G)> 9, and for
\Delta> 6 when triangles sharing a vertex are forbidden
and when 4-cycles are forbidden.
We have improved these results in two ways. If G is a planar graph with no 3-faces sharing an edge and \Delta(G) > 7, then G is (\Delta(G)+1)-edge-choosable. We also show that if G is a planar graph with \Delta(G) = 5 and G has no 4-cycles then G is 6-edge-choosable. Both of our results use discharging. |
| Title: | On set edge-choosability |
| Speaker: | Weiting Cao |
| University of Illinois at Urbana-Champaign | |
| Date: | November 29, 2005 |
| Abstract: |
A graph is (r,s)-colorable if we can assign each vertex an
s-subset of [r] such that adjacent vertices receive disjoint
sets. It is (r,s)-choosable if such a coloring can be chosen
whenever each vertex has a list of r available colors (instead of
always the same set [r]). A graph is (r,s)-edge-choosable if
its line graph is (r,s)-choosable.
For a simple graph G and a fixed integer s, we seek the minumum r such that G is (r,s)-edge-choosable. We prove that the Petersen graph is (7,2)-edge-choosable and that every 3-edge-colorable graph is (7,2)-edge-choosable. It remains open whether all graphs with maximum degree 3 are (7,2)-edge-choosable. This is joint work with Daniel Cranston. |
| Title: | On the poset of H-linkage properties |
| Speaker: | Qi Liu |
| University of Illinois at Urbana-Champaign | |
| Date: | December 6, 2005 |
| Abstract: |
Given a fixed multigraph H with vertices
h1,...,hm, a graph G is
H-linked if whenever v1,...,vm are
vertices in G, there is a subdivision of H in G in
which, for all i, vi is the branch vertex
representing hi. We prove some results about when being
H1-linked implies being H2-linked and
when it does not.
This is joint work with Douglas B. West and Gexin Yu. |