Canonical decompositions of 3-connected graphs

DOI10.1109/FOCS57990.2023.00115MaRDI QIDQ6509476arXivFDO

Authors Johannes Carmesin, Jan Kurkofka

Mathematics Subject Classification ID

Connectivity (05C40) Structural characterization of families of graphs (05C75) Graph minors (05C83) Group actions on combinatorial structures (05E18)

Abstract: 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 $K_{3,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.

This page was built for publication: Canonical decompositions of 3-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509476)