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

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.

Series: Graph Theory Seminar

A Roman dominating function of a graph G is a function f which maps
V(G) to {0, 1, 2} such that whenever f(v)=0, there exists a
vertex u adjacent to v such that f(u)=2. The weight
of f is w(f) = \sum_{v \in V(G)} f(v). The Roman
domination number \gamma_R(G) of G is the minimum weight of a
Roman dominating function of G. Chambers, Kinnersley, Prince and
West conjectured that \gamma_R(G) is at most the ceiling 2n/3
for any 2-connected graph G of n vertices.
In this talk, we will give counter-examples to the conjecture, and
proves that
\gamma_R(G) is at most the maximum among the ceiling of 2n/3 and 23n/34
for any 2-connected graph G of n vertices.
This is joint work with Gerard Jennhwa Chang.

Series: Graph Theory Seminar

Arguably, the overarching scientific challenge facing the area of networked robot systems is that of going from local rules to global behaviors in a predefined and stable manner. In particular, issues stemming from the network topology imply that not only must the individual agents satisfy some performance constraints in terms of their geometry, but also in terms of the combinatorial description of the network. Moreover, a multi-agent robotic network is only useful inasmuch as the agents can be redeployed and reprogrammed with relative ease, and we address these two issues (local interactions and programmability) from a controllability point-of-view. In particular, the problem of driving a collection of mobile robots to a given target destination is studied, and necessary conditions are given for this to be possible, based on tools from algebraic graph theory. The main result will be a necessary condition for an interaction topology to be controllable given in terms of the network's external, equitable partitions.

Series: Graph Theory Seminar

Steinberg's Conjecture states that any planar graph without cycles of
length four or five is three colorable. Borodin, Glebov, Montassier,
and Raspaud showed that planar graphs without cycles of length four,
five, or seven are three colorable and Borodin and Glebov showed that
planar graphs without five cycles or triangles at distance at most two
apart are three colorable. We prove a statement similar to both of
these results: that any planar graph with no cycles of length four
through six or cycles of length seven with incident triangles distance
exactly two apart are three colorable. Special thanks to Robin Thomas
for substantial contributions in the development of the proof.

Series: Graph Theory Seminar

A characterization of graphs without an odd cycle is easy, of course,it is exactly bipartite. However, graphs without two vertex disjoint oddcycles are not so simple. Lovasz is the first to give a proof of the twodisjoint odd cycles theorem which characterizes internally 4-connectedgraphs without two vertex disjoint odd cycles. Note that a graph $G$ iscalled internally 4-connected if $G$ is 3-connected, and all 3-cutseparates only one vertex from the other.However, his proof heavily depends on the seminal result by Seymour fordecomposing regular matroids. In this talk, we give a new proof to thetheorem which only depends on the two paths theorem, which characterizesgraphs without two disjoint paths with specified ends (i.e., 2-linkedgraphs). In addition, our proof is simpler and shorter.This is a joint work with K. Kawarabayashi (National Institute ofInformatics).

Series: Graph Theory Seminar

The property that a graph has an embedding in projective plane is closed
under taking minors. So by the well known theorem of Robertson and Seymour,
there exists a finite list of minor-minimal graphs, call it L, such that a
given graph G is projective planar if and only if G does not contain any
graph isomorphic to a member of L as a minor. Glover, Huneke and Wang found
35 graphs in L, and Archdeacon proved that those are all the members of L.
In this talk we show a new
strategy for finding the list L. Our approach is based on conditioning on
the connectivity of a member of L. Assume G is a member of L. If G is not
3-connected then the structure of G is well understood. In the case that G
is 3-connected, the problem breaks down into two main cases, either G has an
internal separation of order three or G is internally 4-connected . In this
talk we find the set of all 3-connected minor minimal non-projective planar
graphs with an internal 3-separation.
This is joint work with Luke Postle and Robin Thomas.

Series: Graph Theory Seminar

This lecture will conclude the series. In a climactic finish the speaker will prove the Unique Linkage Theorem, thereby completing the proof of correctness of the Disjoint Paths Algorithm.

Series: Graph Theory Seminar

First-Fit is an online algorithm that partitions the elements of a poset
into chains. When presented with a new element x, First-Fit adds x
to the first chain whose elements are all comparable to x. In 2004,
Pemmaraju, Raman, and Varadarajan introduced the Column Construction
Method to prove that when P is an interval order of width w,
First-Fit partitions P into at most 10w chains. This bound was
subsequently improved to 8w by Brightwell, Kierstead, and Trotter, and
independently by Narayanaswamy and Babu.
The poset r+s is the disjoint union of a chain of size r and a chain
of size s. A poset is an interval order if and only if it does not
contain 2+2 as an induced subposet. Bosek, Krawczyk, and Szczypka
proved that if P is an (r+r)-free poset of width w, then First-Fit
partitions P into at most 3rw^2 chains and asked whether the bound
can be improved from O(w^2) to O(w). We answer this question in
the affirmative. By generalizing the Column Construction Method, we
show that if P is an (r+s)-free poset of width w, then First-Fit
partitions P into at most 8(r-1)(s-1)w chains.
This is joint work with Gwena\"el Joret.