A unified Erdős-Pósa theorem for constrained cycles
A (Γ1,Γ2)-labeled graph is an oriented graph with its edges labeled by elements of the direct sum of two groups Γ1,Γ2. A cycle in such a labeled graph is (Γ1,Γ2)-non-zero if it is non-zero in both coordinates. Our main result is a generalization of the Flat Wall Theorem of Robertson and Seymour to (...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
2019
|
| In: |
Combinatorica
Year: 2019, Volume: 39, Issue: 1, Pages: 91-133 |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-017-3683-z |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1007/s00493-017-3683-z
|
| Author Notes: | Tony Huynh, Felix Joos, Paul Wollan |
| Summary: | A (Γ1,Γ2)-labeled graph is an oriented graph with its edges labeled by elements of the direct sum of two groups Γ1,Γ2. A cycle in such a labeled graph is (Γ1,Γ2)-non-zero if it is non-zero in both coordinates. Our main result is a generalization of the Flat Wall Theorem of Robertson and Seymour to (Γ1,Γ2)-labeled graphs. As an application, we determine all canonical obstructions to the Erdős-Pósa property for (Γ1,Γ2)-non-zero cycles in (Γ1,Γ2)-labeled graphs. The obstructions imply that the half-integral Erdős-Pósa property always holds for (Γ1,Γ2)-non-zero cycles. |
|---|---|
| Item Description: | Online first 14 August 2018 Gesehen am 27.07.2022 |
| Physical Description: | Online Resource |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-017-3683-z |