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

Series: Graph Theory Seminar

A signed graph is a pair $(G,\Sigma)$ where $G$ is an undirected graph (in which

parallel edges are permitted, but loops are not) and $\Sigma \subseteq E(G)$.

The edges in $\Sigma$ are called odd and the other edges are called even. A

cycle of $G$ is called odd if it has an odd number of odd edges. If $U\subseteq

V(G)$, then re-signing $(G,\Sigma)$ on $U$ gives the signed graph

$(G,\Sigma\Delta \delta(U))$. A signed graph is a minor of $(G,\Sigma)$ if it

comes from $(G,\Sigma)$ by a series of re-signing, deletions of edges and

isolated vertices, and contractions of even edges.

parallel edges are permitted, but loops are not) and $\Sigma \subseteq E(G)$.

The edges in $\Sigma$ are called odd and the other edges are called even. A

cycle of $G$ is called odd if it has an odd number of odd edges. If $U\subseteq

V(G)$, then re-signing $(G,\Sigma)$ on $U$ gives the signed graph

$(G,\Sigma\Delta \delta(U))$. A signed graph is a minor of $(G,\Sigma)$ if it

comes from $(G,\Sigma)$ by a series of re-signing, deletions of edges and

isolated vertices, and contractions of even edges.

If $(G,\Sigma)$ is a signed graph with $n$ vertices, $S(G,\Sigma)$ is the set of

all symmetric $n\times n$ matrices $A=[a_{i,j}]$ with $a_{i,j} > 0$ if $i$ and

$j$ are connected by only odd edges, $a_{i,j} < 0$ if $i$ and $j$ are connected

by only even edges, $a_{i,j}\in \mathbb{R}$ if $i$ and $j$ are connected by

both even and odd edges, $a_{i,j}=0$ if $i$ and $j$ are not connected by any

edges, and $a_{i,i} \in \mathbb{R}$ for all vertices $i$.

The stable inertia set, $I_s(G,\Sigma)$, of a signed graph $(G,\Sigma)$ is the

set of all pairs $(p,q)$ such that there exists a matrix $A\in S(G,\Sigma)$

that has the Strong Arnold Hypothesis, and $p$ positive and $q$ negative

eigenvalues. The stable inertia set of a signed graph forms a generalization of

$\mu(G)$, $\nu(G)$ (introduced by Colin de Verdi\`ere), and $\xi(G)$

(introduced by Barioli, Fallat, and Hogben).

A specialization of $I_s(G,\Sigma)$ is $\nu(G,\Sigma)$, which is defined as the

maximum of the nullities of positive definite matrices $A\in S(G,\Sigma)$ that

have the Strong Arnold Hypothesis.

This invariant is closed under taking minors, and characterizes signed graphs

with no odd cycles as those signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq

1$, and signed graphs with no odd-$K_4$- and no odd-$K^2_3$-minor as those

signed graphs $(G,\Sigma)$ with $\nu(G,\Sigma)\leq 2$. In this talk we will

discuss $I_s(G,\Sigma)$, $\nu(G,\Sigma)$ and these characterizations.

Joint work with Marina Arav, Frank Hall, and Zhongshan Li.

Series: Graph Theory Seminar

Over the past 40 years, researchers

have made many connections between the

dimension of posets and the issue of planarity

for graphs and diagrams, but there appears

to be little work connecting

dimension to structural graph theory. This situation

has changed dramatically in the last several months. At the Robin Thomas birthday conference, Gwenael

Joret, made the following striking conjecture, which

has now been turned into a theorem: The dimension

of a poset is bounded in terms of its height and the

tree-width of its cover graph. In this talk, I will present the proof of this result. The general contours of

the argument should be accessible to graph theorists and combinatorists (faculty and students) without deep knowledge of either dimension or tree-width.

have made many connections between the

dimension of posets and the issue of planarity

for graphs and diagrams, but there appears

to be little work connecting

dimension to structural graph theory. This situation

has changed dramatically in the last several months. At the Robin Thomas birthday conference, Gwenael

Joret, made the following striking conjecture, which

has now been turned into a theorem: The dimension

of a poset is bounded in terms of its height and the

tree-width of its cover graph. In this talk, I will present the proof of this result. The general contours of

the argument should be accessible to graph theorists and combinatorists (faculty and students) without deep knowledge of either dimension or tree-width.

The proof of the theorem was

accomplished by a team of six researchers: Gwenael Joret, Piotr Micek, Kevin Milans, Tom Trotter,

Bartosz Walczak and Ruidong Wang.

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.

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.

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.

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.

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.

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.

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.