A unified Erdős-Pósa theorem for constrained cycles (Q2416515)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A unified Erdős-Pósa theorem for constrained cycles |
scientific article |
Statements
A unified Erdős-Pósa theorem for constrained cycles (English)
0 references
23 May 2019
0 references
A \((\Gamma_1, \Gamma_2)\)-labeled graph is an oriented graph with its edges labeled by elements of the direct sum of two groups \((\Gamma_1, \Gamma_2)\). The paper provides a canonical set of obstructions to the Erdős-Pósa results for \((\Gamma_1, \Gamma_2)\)-non-zero cycles [\textit{P. Erdős} and \textit{L. Pósa}, Publ. Math. 9, 3--12 (1962; Zbl 0133.16701)]. The notion of \(\Gamma\)-odd clique minors is introduced and a structure theorem for $\Gamma$-labeled graphs without a \(\Gamma\)-odd clique minor is proved. A structure theorem, which is a refinement of the flat wall theorem, is established for \((\Gamma_1, \Gamma_2)\)-group-labeled graphs.
0 references
labeled graph
0 references
oriented graph
0 references
constrained cycles
0 references
flat wall theorem
0 references
packing
0 references
Erdős-Pósa property
0 references