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

Series: Graph Theory Seminar

We show that any n-vertex complete graph with edges colored with three
colors contains a set of at most four vertices such that the number of the
neighbors of these vertices in one of the colors is at least 2n/3. The
previous best value proved by Erdos et al in 1989 is 22. It is conjectured
that three vertices suffice. This is joint work with Daniel Kral,
Chun-Hung Liu, Jean-Sebastien Sereni, and Zelealem Yilma.

Series: Graph Theory Seminar

A graph $G$ contains a graph $H$ as an immersion if there exist distinct vertices $\pi(v) \in V(G)$ for every vertex $v \in V(H)$ and paths $P(e)$ in $G$ for every $e \in E(H)$ such that the path $P(uv)$ connects the vertices $\pi(u)$ and $\pi(v)$ in $G$ and furthermore the paths $\{P(e):e \in E(H)\}$ are pairwise edge disjoint. Thus, graph immersion can be thought of as a generalization of subdivision containment where the paths linking the pairs of branch vertices are required to be pairwise edge disjoint instead of pairwise internally vertex disjoint. We will present a simple structure theorem for graphs excluding a fixed $K_t$ as an immersion. The structure theorem gives rise to a model of tree-decompositions based on edge cuts instead of vertex cuts. We call these decompositions tree-cut decompositions, and give an appropriate definition for the width of such a decomposition. We will present a ``grid" theorem for graph immersions with respect to the tree-cut width.
This is joint work with Paul Seymour.

Series: Graph Theory Seminar

In the node-connectivity augmentation problem, we want to add a minimum
number of new edges to an undirected graph to make it k-node-connected.
The complexity of this question is still open, although the analogous questions
of both directed and undirected edge-connectivity and directed
node-connectivity augmentation are known to be polynomially solvable.
I present a min-max formula and a polynomial time algorithm for the
special case when the input graph is already (k-1)-connected. The formula has
been conjectured by Frank and Jordan in 1994.
In the first lecture, I presented previous results on the other connectivity augmentation variants.
In the second part, I shall present my min-max formula and the main ideas of the proof.

Series: Graph Theory Seminar

In the node-connectivity augmentation problem, we want to add a minimum
number of new edges to an undirected graph to make it k-node-connected.
The complexity of this question is still open, although the analogous questions
of both directed and undirected edge-connectivity and directed
node-connectivity augmentation are known to be polynomially solvable.
I present a min-max formula and a polynomial time algorithm for the
special case when the input graph is already (k-1)-connected. The formula has
been conjectured by Frank and Jordan in 1994.
In the first lecture, I shall investigate the background, present some results on the previously
solved connectivity augmentation cases, and exhibit examples motivating the complicated
min-max formula of my paper.

Series: Graph Theory Seminar

Series: Graph Theory Seminar

We consider intersection graphs of
families of straight line segments in the euclidean
plane and show that for every integer k, there is a
family S of line segments so that the intersection graph
G of the family S is triangle-free and has chromatic
number at least k. This result settles a conjecture
of Erdos and has a number of applications to
other classes of intersection graphs.

Series: Graph Theory Seminar

A classical result in graph theory states that, if G is a plane graph,
then G is Eulerian if and only if its dual, G*, is bipartite. I will
talk about an extension of this well-known result to partial duality.
(Where, loosely speaking, a partial dual of an embedded graph G is a graph
obtained by forming the dual with respect to only a subset of edges of G.)
I will extend the above classical connection between bipartite and Eulerian
plane graphs, by providing a necessary and sufficient condition for the
partial dual of a plane graph to be Eulerian or bipartite. I will then go on
to describe how the bipartite partial duals of a plane graph G are
completely characterized by circuits in its medial graph G_m.
This is joint work with Stephen Huggett.

Series: Graph Theory Seminar

Chudnovsky and Seymour's structure theorem for quasi-line graphs has led to
a multitude of recent results that exploit two structural operations: compositions of strips and thickenings. In this paper we prove that
compositions of linear interval strips have a unique optimal strip
decomposition in the absence of a specific degeneracy, and that every
claw-free graph has a unique optimal antithickening, where our two
definitions of optimal are chosen carefully to respect the structural
foundation of the graph. Furthermore, we give algorithms to find the optimal
strip decomposition in O(nm) time and find the optimal antithickening in
O(m2) time. For the sake of both completeness and ease of proof, we
prove stronger results in the more general setting of trigraphs. This gives
a comprehensive "black box" for decomposing quasi-line graphs that is not
only useful for future work but also improves the complexity of some
previous algorithmic results.
Joint work with Maria Chudnovsky.

Series: Graph Theory Seminar

A graph G is k-crossing-critical if it cannot be drawn in plane with fewer than
k crossings, but every proper subgraph of G has such a drawing. We aim to
describe the structure of crossing-critical graphs. In this talk, we review
some of their known properties and combine them to obtain new information
regarding e.g. large faces in the optimal drawings of crossing-critical graphs.
Based on joint work with P. Hlineny and L. Postle.

Series: Graph Theory Seminar

Boros and Furedi (for d=2) and Barany (for arbitrary d) proved that
there exists a constant c_d>0 such that for every set P of n points in R^d
in general position, there exists a point of R^d contained in at least
c_d n!/(d+1)!(n-d-1)! (d+1)-simplices with vertices at the points of P.
Gromov [Geom. Funct. Anal. 20 (2010), 416-526] improved the lower bound
on c_d by topological means. Using methods from extremal combinatorics,
we improve one of the quantities appearing in Gromov's approach and
thereby provide a new stronger lower bound on c_d for arbitrary d.
In particular, we improve the lower bound on c_3 from 0.06332 due to
Matousek and Wagner to more than 0.07509 (the known upper bound on c_3
is 0.09375). Joint work with Lukas Mach and Jean-Sebastien Sereni.