## Seminars and Colloquia by Series

### Large Even Factors of Graphs

Series
Graph Theory Seminar
Time
Thursday, February 9, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Genghua FanCenter for Discrete Mathematics, Fuzhou University
A spanning subgraph $F$ of a graph $G$ iscalled an even factor of $G$ if each vertex of $F$ has even degreeat least 2 in $F$. It was proved that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)$, which is best possible. Recently, Cheng et al.extended the result by considering vertices of degree 2. They provedthat if a graph $G$ has an even factor, then it has an even factor$F$ with $|E(F)|\geq {4\over 7}(|E(G)| + 1)+{1\over 7}|V_2(G)|$,where $V_2(G)$ is the set of vertices of degree 2 in $G$. They alsogave examples showing that the second coefficient cannot be largerthan ${2\over 7}$ and conjectured that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)+ {2\over 7}|V_2(G)|$. We note that the conjecture isfalse if $G$ is a triangle. We confirm the conjecture for all graphson at least 4 vertices. Moreover, if $|E(H)|\leq {4\over 7}(|E(G)| +1)+ {2\over 7}|V_2(G)|$ for every even factor $H$ of $G$, then everymaximum even factor of $G$ is a 2-factor in which each component isan even circuit.

### Chip firing and divisorial graph gonality

Series
Graph Theory Seminar
Time
Thursday, January 19, 2017 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dion GijswijtTU Delft
Consider the following solitaire game on a graph. Given a chip configuration on the node set V, a move consists of taking a subset U of nodes and sending one chip from U to V\U along each edge of the cut determined by U. A starting configuration is winning if for every node there exists a sequence of moves that allows us to place at least one chip on that node. The (divisorial) gonality of a graph is defined as the minimum number of chips in a winning configuration. This notion belongs to the Baker-Norine divisor theory on graphs and can be seen as a combinatorial analog of gonality for algebraic curves. In this talk we will show that the gonality is lower bounded by the tree-width and, if time permits, that the parameter is NP-hard to compute. We will conclude with some open problems.

### Domination in tournaments

Series
Graph Theory Seminar
Time
Thursday, November 3, 2016 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Chun-Hung LiuPrinceton University
A tournament is a directed graph obtained by orienting each edge of a complete graph. A set of vertices D is a dominating set in a tournament if every vertex not in D is pointed by a vertex in D. A tournament H is a rebel if there exists k such that every H-free tournament has a dominating set of size at most k. Wu conjectured that every tournament is a rebel. This conjecture, if true, implies several other conjectures about tournaments. However, we will prove that Wu's conjecture is false in general and prove a necessary condition for being rebels. In addition, we will prove that every 2-colorable tournament and at least one non-2-colorable tournament are rebels. The later implies an open case of a conjecture of Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott, Seymour and Thomasse about coloring tournaments. This work is joint with Maria Chudnovsky, Ringi Kim, Paul Seymour and Stephan Thomasse.

### Graph Hausdorff dimension, Kolmogorov complexity and construction of fractal graphs

Series
Graph Theory Seminar
Time
Thursday, October 13, 2016 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Pavel SkumsDepartment of Computer Science, Georgia State University
Lately there was a growing interest in studying self-similarity and fractal properties of graphs, which is largely inspired by applications in biology, sociology and chemistry. Such studies often employ statistical physics methods that borrow some ideas from graph theory and general topology, but are not intended to approach the problems under consideration in a rigorous mathematical way. To the best of our knowledge, a rigorous combinatorial theory that defines and studies graph-theoretical analogues of topological fractals still has not been developed. In this paper we introduce and study discrete analogues of Lebesgue and Hausdorff dimensions for graphs. It turned out that they are closely related to well-known graph characteristics such as rank dimension and Prague (or Nesetril-Rodl) dimension. It allowed us to formally define fractal graphs and establish fractality of some graph classes. We show, how Hausdorff dimension of graphs is related to their Kolmogorov complexity. We also demonstrate fruitfulness of this interdisciplinary approach by discover a novel property of general compact metric spaces using ideas from hypergraphs theory and by proving an estimation for Prague dimension of almost all graphs using methods from algorithmic information theory.

### Decomposition of graphs under average degree condition

Series
Graph Theory Seminar
Time
Thursday, September 29, 2016 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Stiebitz showed that a graph with minimum degree s+t+1 can be decomposed into vertex disjoint subgraphs G_1 and G_2 such that G_1 has minimum degree at least s and G_2 has minimum degree at least t. Motivated by this result, Norin conjectured that a graph with average degree s+t+2 can be decomposed into vertex disjoint subgraphs G_1 and G_2 such that G_1 has average degree at least s and G_2 has average degree at least t. Recently, we prove that a graph with average degree s+t+2 contains vertex disjoint subgraphs G_1 and G_2 such that G_1 has average degree at least s and G_2 has average degree at least t. In this talk, I will discuss the proof technique. This is joint work with Hehui Wu.

### Decomposition of Triangle-dense Graphs

Series
Graph Theory Seminar
Time
Wednesday, April 20, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
He GuoMath, GT
A special feature possessed by the graphs of social networks is triangle-dense. R. Gupta, T. Roughgarden and C. Seshadhri give a polynomial time graph algorithm to decompose a triangle-dense graph into some clusters preserving high edge density and high triangle density in each cluster with respect to the original graph and each cluster has radius 2. And high proportion of triangles of the original graph are preserved in these clusters. Furthermore, if high proportion of edges in the original graph is "locally triangle-dense", then additionally, high proportion of edges of the original graph are preserved in these clusters. In this talk, I will present most part of the paper "Decomposition of Triangle-dense Graphs" in SIAM J. COMPUT. Vol. 45, No. 2, pp. 197–215, 2016, by R. Gupta, T. Roughgarden and C. Seshadhri.

### The Kelmans-Seymour conjecture V: no contractible edges or triangles (finding TK_5)

Series
Graph Theory Seminar
Time
Wednesday, April 13, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we study the structure of these 5-separations and 6-separations, and prove the Kelmans-Seymour conjecture.

### The Kelmans-Seymour conjecture V: no contractible edges or triangles (first part)

Series
Graph Theory Seminar
Time
Wednesday, April 6, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Yan WangMath, GT
Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we prove a lemma using the characterization of three paths with designated ends, which will be used in the proof of the Kelmans-Seymour conjecture.

### The Kelmans-Seymour conjecture IV: 3-vertices in K_4^-

Series
Graph Theory Seminar
Time
Wednesday, March 30, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dawei HeMath, GT
Let G be a 5-connected graph and let x1, x2,y1,y2 in V(G) be distinct, such that G[{x1, x2, y1, y2}] is isomorphic to K_4^- and y1y2 is not in E(G). We show that G contains a K_4^- in which x1 is of degree 2, or G-x1 contains K_4^-, or G contains a TK_5 in which x1 is not a branch vertex, or {x2, y1, y2} may be chosen so that for any distinct w1,w2 in N(x1) - {x2, y1, y2}, G - {x1v : v is not in {w1, w2, x2, y1,y2} } contains TK_5.

### On Reed's conjecture

Series
Graph Theory Seminar
Time
Wednesday, March 16, 2016 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Luke PostleDepartment of C&amp;amp;O, University of Waterloo
In 1998, Reed proved that the chromatic number of a graph is bounded away from its trivial upper bound, its maximum degree plus one, and towards its trivial lower bound, its clique number. Reed also conjectured that the chromatic number is at most halfway in between these two bounds. We prove that for large maximum degree, that the chromatic number is at least 1/25th in between. Joint work with Marthe Bonamy and Tom Perrett.