TY - UNPB
T1 - Canonical decompositions of 3-connected graphs
AU - Carmesin, Johannes
AU - Kurkofka, Jan
PY - 2023/4/3
Y1 - 2023/4/3
N2 - We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or thickened K3,m 's. Our construction is explicit, canonical, and has the following applications: we obtain a new theorem characterising all Cayley graphs as either essentially 4-connected, cycles, or complete graphs on at most four vertices, and we provide an automatic proof of Tutte's wheel theorem.
AB - We offer a new structural basis for the theory of 3-connected graphs, providing a unique decomposition of every such graph into parts that are either quasi 4-connected, wheels, or thickened K3,m 's. Our construction is explicit, canonical, and has the following applications: we obtain a new theorem characterising all Cayley graphs as either essentially 4-connected, cycles, or complete graphs on at most four vertices, and we provide an automatic proof of Tutte's wheel theorem.
U2 - 10.48550/arXiv.2304.00945
DO - 10.48550/arXiv.2304.00945
M3 - Preprint
BT - Canonical decompositions of 3-connected graphs
PB - arXiv
ER -