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 (...
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
2019
|
| In: |
Combinatorica
Year: 2019, Jahrgang: 39, Heft: 1, Pages: 91-133 |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-017-3683-z |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1007/s00493-017-3683-z
|
| Verfasserangaben: | Tony Huynh, Felix Joos, Paul Wollan |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Online first 14 August 2018 Gesehen am 27.07.2022 |
| Beschreibung: | Online Resource |
| ISSN: | 1439-6912 |
| DOI: | 10.1007/s00493-017-3683-z |