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
    0 references
    0 references
    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

    Identifiers