Georgia Institute of Technology College of Sciences

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.

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.

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.

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.