6-connected graphs are two-three 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 6-connected 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, 2017-10-04)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 human-in-the-loop network ... -
Finding Dense Regions of Rapidly Changing Graphs
Gabert, Kasimir Georg (Georgia Institute of Technology, 2022-05-02)Many of today's massive and rapidly changing graphs contain internal structure---hierarchies of locally dense regions---and finding and tracking this structure is key to detecting emerging behavior, exposing internal activity, ... -
Graph analysis of streaming relational data
Zakrzewska, Anita N. (Georgia Institute of Technology, 2018-04-13)Graph analysis can be used to study streaming data from a variety of sources, such as social networks, financial transactions, and online communication. The analysis of streaming data poses many challenges, including dealing ...