- You are here:
- GT Home
- Home
- News & Events
Series: Graph Theory Seminar
Let G be a graph containing 5 different vertices a0, a1, a2, b1 and
b2. We say that (G, a0, a1, a2, b1, b2) is feasible if G contains
disjoint connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1) and
{b1, b2}⊆V(G2). In this talk, we will introduce
ideal frames, slim connectors and fat connectors. We will first deal
with the ideal frames without fat connectors, by studying 3-edge and
5-edge configurations. Joint work with Changong Li, Robin Thomas, and
Xingxing Yu.
Series: Graph Theory Seminar
Let G be a graph containing 5 different vertices a0, a1, a2, b1
and b2. We say that (G, a0, a1, a2, b1, b2) is feasible if G contains
disjoint connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1) and
{b1, b2}⊆V(G2). In this talk, we will describe
the structure of G when (G, a0, a1, a2, b1, b2) is infeasible, using
frames and connectors. Joint work with Changong Li, Robin Thomas, and
Xingxing Yu.
Series: Graph Theory Seminar
In this talk we will discuss some Tur\'an-type results on graphs with a given circumference.
Let $W_{n,k,c}$ be the graph obtained from a clique $K_{c-k+1}$
by adding $n-(c-k+1)$ isolated vertices each joined to the same $k$ vertices of the clique,
and let $f(n,k,c)=e(W_{n,k,c})$.
Kopylov proved in 1977 that for $c\max\{f(n,3,c),f(n,\lfloor\frac{c}{2}\rfloor-1,c)\}$,
then either $G$ is a subgraph of $W_{n,2,c}$ or $W_{n,\lfloor\frac{c}{2}\rfloor,c}$,
or $c$ is odd and $G$ is a subgraph of a member of two well-characterized families
which we define as $\mathcal{X}_{n,c}$ and $\mathcal{Y}_{n,c}$.
We extend and refine their result by showing that if $G$ is a 2-connected graph on $n$
vertices with minimum degree at least $k$ and circumference $c$
such that $10\leq c\max\{f(n,k+1,c),f(n,\lfloor\frac{c}{2}\rfloor-1,c)\}$,
then one of the following holds:\\
(i) $G$ is a subgraph of $W_{n,k,c}$ or $W_{n,\lfloor\frac{c}{2}\rfloor,c}$, \\
(ii) $k=2$, $c$ is odd, and $G$ is a subgraph of a member of $\mathcal{X}_{n,c}\cup \mathcal{Y}_{n,c}$, or \\
(iii) $k\geq 3$ and $G$ is a subgraph of the union of a clique $K_{c-k+1}$ and some cliques $K_{k+1}$'s,
where any two cliques share the same two vertices.
This provides a unified generalization of the above result of F\"{u}redi et al. as well as
a recent result of Li et al. and independently, of F\"{u}redi et al. on non-Hamiltonian graphs.
Moreover, we prove a stability result on a classical theorem of Bondy on the circumference.
We use a novel approach, which combines several proof ideas including a closure operation and an edge-switching technique.
Series: Graph Theory Seminar
Let G be a graph containing 5 different vertices a0, a1, a2, b1 and b2.
We say that (G, a0, a1, a2, b1, b2) is feasible if G contains disjoint
connected subgraphs G1, G2, such that {a0, a1, a2}⊆V(G1)
and {b1, b2}⊆V(G2).
In this talk, we will continue our discussion on
the operations we use for characterizing feasible (G, a0, a1, a2, b1,
b2). If time permits, we will also discuss useful structures for
obtaining that characterization, such as frame, ideal frame, and
framework. Joint work with Changong Li, Robin Thomas, and
Xingxing Yu.
Series: Graph Theory Seminar
Let $G$ be a graph containing 5 different vertices $a_0, a_1, a_2, b_1$ and $b_2$. We say that $(G,a_0,a_1,a_2,b_1,b_2)$ is feasible if $G$ contains disjoint connected subgraphs $G_1, G_2$, such that $\{a_0, a_1, a_2\}\subseteq V(G_1)$ and $\{b_1, b_2\}\subseteq V(G_2)$. We give a characterization for $(G,a_0,a_1,a_2,b_1,b_2)$ to be feasible, answering a question of Robertson and Seymour. This is joint work with Changong Li, Robin Thomas, and Xingxing Yu.In this talk, we will discuss the operations we will use to reduce $(G,a_0,a_1,a_2,b_1,b_2)$ to $(G',a_0',a_1',a_2',b_1',b_2')$ with $|V(G)|+|E(G)|>|V(G')|+E(G')$, such that $(G,a_0,a_1,a_2,b_1,b_2)$ is feasible iff $(G',a_0',a_1',a_2'b_1',b_2')$ is feasible.
Series: Graph Theory Seminar
We study the uniqueness of optimal configurations in extremal
combinatorics. An empirical experience suggests that optimal solutions to
extremal graph theory problems can be made asymptotically unique by
introducing additional constraints. Lovasz conjectured that this phenomenon
is true in general: every finite feasible set of subgraph density
constraints can be extended further by a finite set of density constraints
such that the resulting set is satisfied by an asymptotically unique graph.
We will present a counterexample to this conjecture and discuss related
results.
The talk is based on joint work with Andrzej Grzesik and Laszlo Miklos
Lovasz.
Series: Graph Theory Seminar
For a graph G, the Colin de Verdière graph parameter mu(G) is the maximum
corank of any matrix in a certain family of generalized adjacency matrices
of G. Given a non-negative integer t, the family of graphs with mu(G) <= t
is minor-closed and therefore has some nice properties. For example, a
graph G is planar if and only if mu(G) <= 3. Colin de Verdière conjectured
that the chromatic number chi(G) of a graph satisfies chi(G) <= mu(G)+1.
For graphs with mu(G) <= 3 this is the Four Color Theorem. We conjecture
that if G has at least t vertices and mu(G) <= t, then |E(G)| <= t|V(G)| -
(t+1 choose 2). For planar graphs this says |E(G)| <= 3|V(G)|-6. If this
conjecture is true, then chi(G) <= 2mu(G). We prove the conjectured edge
upper bound for certain classes of graphs: graphs with mu(G) small, graphs
with mu(G) close to |V(G)|, chordal graphs, and the complements of chordal
graphs.
Series: Graph Theory Seminar
A spanning subgraph $F$ of a graph $G$ iscalled an even factor of $G$ if each vertex of $F$ has even degreeat least 2 in $F$. It was proved that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)$, which is best possible. Recently, Cheng et al.extended the result by considering vertices of degree 2. They provedthat if a graph $G$ has an even factor, then it has an even factor$F$ with $|E(F)|\geq {4\over 7}(|E(G)| + 1)+{1\over 7}|V_2(G)|$,where $V_2(G)$ is the set of vertices of degree 2 in $G$. They alsogave examples showing that the second coefficient cannot be largerthan ${2\over 7}$ and conjectured that if a graph $G$ has an evenfactor, then it has an even factor $F$ with $|E(F)|\geq {4\over7}(|E(G)| + 1)+ {2\over 7}|V_2(G)|$. We note that the conjecture isfalse if $G$ is a triangle. We confirm the conjecture for all graphson at least 4 vertices. Moreover, if $|E(H)|\leq {4\over 7}(|E(G)| +1)+ {2\over 7}|V_2(G)|$ for every even factor $H$ of $G$, then everymaximum even factor of $G$ is a 2-factor in which each component isan even circuit.
Series: Graph Theory Seminar
Consider the following solitaire game on a graph. Given a chip configuration on the node set V, a move consists of taking a subset U of nodes and sending one chip from U to V\U along each edge of the cut determined by U. A starting configuration is winning if for every node there exists a sequence of moves that allows us to place at least one chip on that node. The (divisorial) gonality of a graph is defined as the minimum number of chips in a winning configuration. This notion belongs to the Baker-Norine divisor theory on graphs and can be seen as a combinatorial analog of gonality for algebraic curves. In this talk we will show that the gonality is lower bounded by the tree-width and, if time permits, that the parameter is NP-hard to compute. We will conclude with some open problems.
Series: Graph Theory Seminar
A tournament is a directed graph obtained by orienting each edge of a
complete graph. A set of vertices D is a dominating set in a tournament
if every vertex not in D is pointed by a vertex in D. A tournament H is a
rebel if there exists k such that every H-free tournament has a
dominating set of size at most k. Wu conjectured that every tournament
is a rebel. This conjecture, if true, implies several other conjectures
about tournaments. However, we will prove that Wu's conjecture is false
in general and prove a necessary condition for being rebels. In
addition, we will prove that every 2-colorable tournament and at least
one non-2-colorable tournament are rebels. The later implies an open
case of a conjecture of Berger, Choromanski, Chudnovsky, Fox, Loebl,
Scott, Seymour and Thomasse about coloring tournaments. This work is
joint with Maria Chudnovsky, Ringi Kim, Paul Seymour and Stephan
Thomasse.
