6-connected graphs are two-three linked

Graph theory;Disjoint paths in graphs;Two-three linked graphs;6-connected graphs

Xie, Shijie ; Yu, Xingxing Mathematics Thomas, Robin Tetali, Prasad Peng, Richard Warnke, Lutz ; Yu, Xingxing

University:Georgia Institute of Technology

Department:Mathematics

关键词: Graph theory;    Disjoint paths in graphs;    Two-three linked graphs;    6-connected graphs;   

Others  :  https://smartech.gatech.edu/bitstream/1853/62273/1/XIE-DISSERTATION-2019.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

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.