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

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. The conjecture
is still open for Δ=4. We show the conjecture is true when an edge cut
of size 1 or 2 exists, and in certain cases when an edge cut of size 4
or 3 exists.

Series: Graph Theory Working Seminar

Let $\nu$ denote the maximum size of a packing of edge-disjoint triangles in a graph $G$. We can clearly make $G$ triangle-free by deleting $3\nu$ edges. Tuza conjectured in 1981 that $2\nu$ edges suffice, and proved it for planar graphs. The best known general bound is $(3-\frac{3}{23})\nu$ proven by Haxell in 1997. We will discuss this proof and some related results.

Series: Graph Theory Working Seminar

Let $g(n) = \max_{|T| = n}|\text{Aut}(T)|$ where $T$ is a tournament. Goldberg and Moon conjectured that $g(n) \le \sqrt{3}^{n-1}$ for all $n \ge 1$ with equality holding if and only if $n$ is a power of 3. Dixon proved the conjecture using the Feit-Thompson theorem. Alspach later gave a purely combinatorial proof. We discuss Alspach's proof and and some of its applications.

Series: Graph Theory Working Seminar

Series: Graph Theory Working Seminar

<p>Strong edge coloring of a graph $G$ is a coloring of the edges of the graph such that each color class is an induced subgraph. The strong chromatic index of $G$ is the smallest number $k$ such that $G$ has a $k$-strong edge coloring. Erdős and Nešetřil conjecture that the strong chromatic index of a graph of max degree $\Delta$ is at most $5\Delta^2/4$ if $\Delta$ is even and $(5\Delta^2-2\Delta + 1)/4$ if $\Delta$ is odd. It is known for $\Delta=3$ that the conjecture holds, and in this talk I will present part of Anderson's proof that the strong chromatic index of a subcubic planar graph is at most $10$</p>

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.