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

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.

Series: Graph Theory Seminar

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.

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.

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.

Series: Graph Theory Seminar

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.

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.