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

Series: Graph Theory Seminar

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.

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.

Series: Graph Theory Seminar

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.

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.

Series: Graph Theory Seminar

We use K_4^- to denote the graph obtained from K_4 by removing an edge,and

use TK_5 to denote a subdivision of K_5. Let G be a 5-connected nonplanar

graph and {x_1, x_2, y_1, y_2} \subseteq V (G) such that G[{x_1,x_2, y_1,

y_2}] = K_4^- with y_1y_2 \in E(G). Let w_1,w_2,w_3 \in N(y_2)- {x_1,x_2}

be distinct. We show that G contains a TK_5 in which y_2 is not a branch

vertex, or G - y_2 contains K_4^-, or G has a special 5-separation, or G'

:= G - {y_2v : v \in {w_1,w_2,w_3, x_1, x_2}} contains TK_5.In this talk,

we will obtain a substructure in G' and several additional paths in G', and

then use this substructure to find the desired TK_5.

use TK_5 to denote a subdivision of K_5. Let G be a 5-connected nonplanar

graph and {x_1, x_2, y_1, y_2} \subseteq V (G) such that G[{x_1,x_2, y_1,

y_2}] = K_4^- with y_1y_2 \in E(G). Let w_1,w_2,w_3 \in N(y_2)- {x_1,x_2}

be distinct. We show that G contains a TK_5 in which y_2 is not a branch

vertex, or G - y_2 contains K_4^-, or G has a special 5-separation, or G'

:= G - {y_2v : v \in {w_1,w_2,w_3, x_1, x_2}} contains TK_5.In this talk,

we will obtain a substructure in G' and several additional paths in G', and

then use this substructure to find the desired TK_5.

Series: Graph Theory Seminar

We use K_4^- to denote the graph obtained from K_4 by removing an edge,and use TK_5 to denote a subdivision of K_5. Let G be a 5-connected nonplanar graph and {x_1, x_2, y_1, y_2} \subseteq V (G) such that G[{x_1,x_2, y_1, y_2}] = K_4^- with y_1y_2 \in E(G). Let w_1,w_2,w_3 \in N(y_2)- {x_1,x_2} be distinct. We show that G contains a TK_5 in which y_2 is not a branch vertex, or G - y_2 contains K_4^-, or G has a special 5-separation, or G - {y_2v : v \in {w_1,w_2,w_3, x_1, x_2}} contains TK_5.In this talk, we will show the existence of a path X in G whose removal does not affect connectivity too much.

Series: Graph Theory Seminar

Seymour and, independently, Kelmans conjectured in the 1970s that

every 5-connected nonplanar graph contains a subdivision of K_5. This

conjecture was proved by Ma and Yu for graphs containing K_4^-. In order to

establish the Kelmans-Seymour conjecture for all graphs, we need to

consider 5-separations and 6-separations with less restrictive structures.

We will talk about special 5-separations and 6-separations whose cut

contains a triangle. Results will be used in subsequently to prove the

Kelmans-Seymour conjecture.

every 5-connected nonplanar graph contains a subdivision of K_5. This

conjecture was proved by Ma and Yu for graphs containing K_4^-. In order to

establish the Kelmans-Seymour conjecture for all graphs, we need to

consider 5-separations and 6-separations with less restrictive structures.

We will talk about special 5-separations and 6-separations whose cut

contains a triangle. Results will be used in subsequently to prove the

Kelmans-Seymour conjecture.

Series: Graph Theory Seminar

Seymour and, independently, Kelmans conjectured in the 1970s that

every 5-connected nonplanar graph contains a subdivision of K_5. This

conjecture was proved by Ma and Yu for graphs containing K_4^-, and an

important step in their proof is to deal with a 5-separation in the graph

with a planar side. In order to establish the Kelmans-Seymour conjecture

for all graphs, we need to consider 5-separations and 6-separations with

less restrictive structures. We will talk about special 5-separations and

6-separations, including those with an apex side. Results will be used in

subsequently to prove the Kelmans-Seymour conjecture.

every 5-connected nonplanar graph contains a subdivision of K_5. This

conjecture was proved by Ma and Yu for graphs containing K_4^-, and an

important step in their proof is to deal with a 5-separation in the graph

with a planar side. In order to establish the Kelmans-Seymour conjecture

for all graphs, we need to consider 5-separations and 6-separations with

less restrictive structures. We will talk about special 5-separations and

6-separations, including those with an apex side. Results will be used in

subsequently to prove the Kelmans-Seymour conjecture.

Series: Graph Theory Seminar

The goal of this talk is to show recent advances regarding two important

mathematical problems. The first one can be straightforwardly formulated in

a graph theory language, but can be possibly applied in other fields. The

second one was motivated by machine learning applications, but leads to

graph theory techniques.

mathematical problems. The first one can be straightforwardly formulated in

a graph theory language, but can be possibly applied in other fields. The

second one was motivated by machine learning applications, but leads to

graph theory techniques.

The celebrated open conjecture of Erdos and Hajnal from 1989 states

that families of graphs not having some given graph H as an induced

subgraph contain polynomial-size cliques/stable sets (in the undirected

setting) or transitive subsets (in the directed setting). Recent techniques

developed over last few years provided the proof of the conjecture for new

infinite classes of graphs (in particular the first infinite class of prime

graphs). Furthermore, they gave tight asymptotics for the Erdos-Hajnal

coefficients for many classes of prime tournaments as well as the proof of

the conjecture for all but one tournament on at most six vertices and the

proof of the weaker version of the conjecture for trees on at most six

vertices. In this part of the talk I will summarize these recent

achievements.

Structured non-linear graph-based hashing is motivated by applications in

neural networks, where matrices of linear projections are constrained to

have a specific structured form. This drastically reduces the size of the

model and speeds up computations. I will show how the properties of the

underlying graph encoding correlations between entries of these matrices

(such as its chromatic number) imply the quality of the entire non-linear

hashing mechanism. Furthermore, I will explain how general structured

matrices that very recently attracted researchers’ attention naturally lead

to the underlying graph theory description.

Series: Graph Theory Seminar

There has been extensive research on cycle lengths in graphs with large

minimum degree. In this talk, we will present several new and tight results

in this area. Let G be a graph with minimum degree at least k+1. We

prove that if G is bipartite, then there are k cycles in G whose

lengths form an arithmetic progression with common difference two. For

general graph G, we show that G contains \lfloor k/2\rfloor cycles

with consecutive even lengths, and in addition, if G is 2-connected and

non-bipartite, then G contains \lfloor k/2\rfloor cycles with

consecutive odd lengths. Thomassen (1983) made two conjectures on cycle

lengths modulo a fixed integer k: (1) every graph with minimum degree at

least k+1 contains cycles of all even lengths modulo k; (2) every

2-connected non-bipartite graph with minimum degree at least $k+1$ contains

cycles of all lengths modulo k. These two conjectures, if true, are best

possible. Our results confirm both conjectures!

when k is even. And when k is odd, we show that minimum degree at

least $+4 suffices. Moreover, our results derive new upper bounds of the

chromatic number in terms of the longest sequence of cycles with

consecutive (even or odd) lengths. This is a joint work with Chun-Hung Liu.

minimum degree. In this talk, we will present several new and tight results

in this area. Let G be a graph with minimum degree at least k+1. We

prove that if G is bipartite, then there are k cycles in G whose

lengths form an arithmetic progression with common difference two. For

general graph G, we show that G contains \lfloor k/2\rfloor cycles

with consecutive even lengths, and in addition, if G is 2-connected and

non-bipartite, then G contains \lfloor k/2\rfloor cycles with

consecutive odd lengths. Thomassen (1983) made two conjectures on cycle

lengths modulo a fixed integer k: (1) every graph with minimum degree at

least k+1 contains cycles of all even lengths modulo k; (2) every

2-connected non-bipartite graph with minimum degree at least $k+1$ contains

cycles of all lengths modulo k. These two conjectures, if true, are best

possible. Our results confirm both conjectures!

when k is even. And when k is odd, we show that minimum degree at

least $+4 suffices. Moreover, our results derive new upper bounds of the

chromatic number in terms of the longest sequence of cycles with

consecutive (even or odd) lengths. This is a joint work with Chun-Hung Liu.

Series: Graph Theory Seminar

A set F of graphs has the Erdos-Posa property if there exists a function

f such that every graph either contains k disjoint subgraphs each

isomorphic to a member in F or contains at most f(k) vertices

intersecting all such subgraphs. In this talk I will address the

Erdos-Posa property with respect to three closely related graph

containment relations: minor, topological minor, and immersion. We

denote the set of graphs containing H as a minor, topological minor and

immersion by M(H),T(H) and I(H), respectively.

f such that every graph either contains k disjoint subgraphs each

isomorphic to a member in F or contains at most f(k) vertices

intersecting all such subgraphs. In this talk I will address the

Erdos-Posa property with respect to three closely related graph

containment relations: minor, topological minor, and immersion. We

denote the set of graphs containing H as a minor, topological minor and

immersion by M(H),T(H) and I(H), respectively.

Robertson and Seymour in 1980's proved that M(H) has the Erdos-Posa

property if and only if H is planar. And they left the question for

characterizing H in which T(H) has the Erdos-Posa property in the same

paper. This characterization is expected to be complicated as T(H) has

no Erdos-Posa property even for some tree H. In this talk, I will

present joint work with Postle and Wollan for providing such a

characterization. For immersions, it is more reasonable to consider an

edge-variant of the Erdos-Posa property: packing edge-disjoint subgraphs

and covering them by edges. I(H) has no this edge-variant of the

Erdos-Posa property even for some tree H. However, I will prove that

I(H) has the edge-variant of the Erdos-Posa property for every graph H

if the host graphs are restricted to be 4-edge-connected. The

4-edge-connectivity cannot be replaced by the 3-edge-connectivity.

Series: Graph Theory Seminar

We discuss the relationship between the chromatic number (Chi),

the clique number (Omega) and maximum average degree (MAD).

the clique number (Omega) and maximum average degree (MAD).