- You are here:
- GT Home
- Home
- News & Events

Series: Graph Theory Working Seminar

Continuing
on the theme mentioned in my recent research horizons lecture, I will
illustrate two techniques by deriving upper and lower bounds on the
number of independent sets in bipartite and triangle-free graphs.

Series: Graph Theory Working Seminar

Continuation of last week's talk. For a graph on n
vertices, a vertex partition A,B,C is a f(n)-vertex separator if |C|≤f(n) and |A|,|B|≤2n/3 and (A,B)=∅. A theorem from Gary Miller states for an embedded 2-connected planar graph with maximum face size d there exists a simple cycle such that it is vertex separator of size at most 2√dn. This has applications in divide and conquer algorithms.

Series: Graph Theory Working Seminar

For a graph on $n$ vertices, a vertex partition $A,B,C$ is a $f(n)$-vertex separator if $|C| \le f(n)$ and $|A|,|B| \le \frac{2}{3}n$ and $(A,B) = \emptyset$. A theorem from Gary Miller states for an embedded 2-connected planar graph with maximum face size $d$ there exists a simple cycle such that it is vertex separator of size at most $2\sqrt{dn}$. This has applications in divide and conquer algorithms.

Series: Graph Theory Working Seminar

A
graph G is H-free if H is not isomorphic to an induced subgraph of G.
Let Pt denote the path on t vertices, and let Kn denote the complete
graph on n vertices. For a positive integer r, we use rG to denote the
disjoint
union of r copies of G. In this talk, we will discuss the result, by
Gaspers and Huang, that (2P2, K4)-free graphs are 4-colorable, where the
bound is attained by the five-wheel and the complement of seven-cycle.
It answers an open question by Wagon in 1980s.

Series: Graph Theory Working Seminar

Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree
Δ can be strong edge colored using at most (5/4)Δ^2 colors. A (Δ_a, Δ_
b)-bipartite graphs is an bipartite
graph such that its components A,B has maximum degree Δ_a, Δ_ b
respectively. R.A. Brualdi and J.J.
Quinn Massey (1993)
conjectured that the strong chromatic index of (Δ_a, Δ_ b)-bipartite
graphs is bounded by Δ_a*Δ_ b. In
this talk, we focus on a recent result affirming the conjecture for (3, Δ)-bipartite
graphs.

Series: Graph Theory Working Seminar

Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most (5/4)Δ^2 colors. In this talk, we focus on a conjecture by R.J. Faudree et al, that Δ^2 holds as a bound for strong chromatic index in bipartite graphs, and related results where a bound is known.

Series: Graph Theory Working Seminar

Erdős and Nešetřil conjectured in 1985 that every graph with maximum degree Δ can be strong edge colored using at most (5/4)Δ^2 colors. In this talk we discuss recent progress made in the case of Δ=4, and go through the method used to improve the upper bound to 21 colors, one away from the conjectured 20.

Series: Graph Theory Working Seminar

A classical result of Edwards says that every m-edge graph has a 2-cut of size m/2+Ω(√m), and this is best possible. We will continue our discussion about recent results on analogues of Edwards’ result and related problems in hypergraphs.

Series: Graph Theory Working Seminar

An $r$-cut of a $k$-uniform hypergraph $H$ is a partition of the vertex set of $H$ into $r$ parts and the size of the cut is the number of edges which have a vertex in each part. A classical result of Edwards says that every $m$-edge graph has a 2-cut of size $m/2+\Omega(\sqrt{m})$, and this is best possible. In this talk we will discuss recent results on analogues of Edwards’ result and related problems in hypergraphs.

Series: Graph Theory Working Seminar

Gallai
conjectured in 1968 that the edges of a connected graph on n vertices
can be decomposed into at most (n+1)/2 edge-disjoint paths. This
conjecture
is still open, even for planar graphs. In this talk we will discuss some
related results and special cases where it is known to hold.