Autor:	Carmesin, Johannes, Kurkofka, Jan
Rok vydání:	2023
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics 05C40 (Primary) 05C75 05C83 05E18 (Secondary)
Druh dokumentu:	Working Paper
DOI:	10.1109/FOCS57990.2023.00115
Popis:	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. Comment: 52 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2304.00945 Zobrazit plný text záznamu View this record from Arxiv