6connected graphs are twothree linked
Abstract
Let $G$ be a graph and $a_0, a_1, a_2, b_1,$ and $b_2$ be distinct vertices of $G$. Motivated by their work on Four Color Theorem, Hadwiger's conjecture for $K_6$, and J\o rgensen's conjecture, Robertson and Seymour asked when does $G$ contain 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 prove that if $G$ is 6connected then such $G_1,G_2$ exist. Joint work with Robin Thomas and Xingxing Yu.
Collections
Related items
Showing items related by title, author, creator and subject.

Adaptive visual network analytics: Algorithms, interfaces, and systems for exploration and querying
Pienta, Robert S. (Georgia Institute of Technology, 20171004)Large graphs are now commonplace, amplifying the fundamental challenges of exploring, navigating, and understanding massive data. Our work tackles critical aspects of graph sensemaking, to create humanintheloop network ... 
Mage: Expressive Pattern Matching in RichlyAttributed Graphs
Pienta, Robert; Tamersoy, Acar; Tong, Hanghang; Chau, Duen Horng (Polo) (Georgia Institute of Technology, 2013)Given a large graph with millions of nodes and edges, say a social graph where both the nodes and edges can have multiple different kinds of attributes (e.g., job titles, tie strengths), how do we quickly find matches ... 
New Tools and Results in Graph Structure Theory
Hegde, Rajneesh (Georgia Institute of Technology, 20060330)We first prove a ``nonembeddable extensions' theorem for polyhedral graph embeddings. Let G be a ``weakly 4connected' planar graph. We describe a set of constructions that produce a finite list of nonplanar graphs, each ...