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 |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1810693233 | ||
| 003 | DE-627 | ||
| 005 | 20220820224229.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 220718s2019 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1007/s00493-017-3683-z |2 doi | |
| 035 | |a (DE-627)1810693233 | ||
| 035 | |a (DE-599)KXP1810693233 | ||
| 035 | |a (OCoLC)1341464150 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 29 |2 sdnb | ||
| 100 | 1 | |a Huynh, Tony |e VerfasserIn |0 (DE-588)1263675662 |0 (DE-627)1811795714 |4 aut | |
| 245 | 1 | 2 | |a A unified Erdős-Pósa theorem for constrained cycles |c Tony Huynh, Felix Joos, Paul Wollan |
| 264 | 1 | |c 2019 | |
| 300 | |a 43 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Online first 14 August 2018 | ||
| 500 | |a Gesehen am 27.07.2022 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a 05C70 | |
| 700 | 1 | |a Joos, Felix |d 1989- |e VerfasserIn |0 (DE-588)1075006171 |0 (DE-627)832846244 |0 (DE-576)442747438 |4 aut | |
| 700 | 1 | |a Wollan, Paul |e VerfasserIn |0 (DE-588)1263675735 |0 (DE-627)1811796028 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Combinatorica |d Berlin : Springer, 1981 |g 39(2019), 1, Seite 91-133 |h Online-Ressource |w (DE-627)253721385 |w (DE-600)1458905-9 |w (DE-576)072372168 |x 1439-6912 |7 nnas |a A unified Erdős-Pósa theorem for constrained cycles |
| 773 | 1 | 8 | |g volume:39 |g year:2019 |g number:1 |g pages:91-133 |g extent:43 |a A unified Erdős-Pósa theorem for constrained cycles |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00493-017-3683-z |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20220718 | ||
| 993 | |a Article | ||
| 994 | |a 2019 | ||
| 998 | |g 1075006171 |a Joos, Felix |m 1075006171:Joos, Felix |p 2 | ||
| 999 | |a KXP-PPN1810693233 |e 4169396820 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"physDesc":[{"extent":"43 S."}],"id":{"doi":["10.1007/s00493-017-3683-z"],"eki":["1810693233"]},"title":[{"title":"A unified Erdős-Pósa theorem for constrained cycles","title_sort":"unified Erdős-Pósa theorem for constrained cycles"}],"type":{"bibl":"article-journal","media":"Online-Ressource"},"origin":[{"dateIssuedDisp":"2019","dateIssuedKey":"2019"}],"relHost":[{"part":{"text":"39(2019), 1, Seite 91-133","issue":"1","extent":"43","pages":"91-133","volume":"39","year":"2019"},"language":["eng"],"pubHistory":["1.1981 -"],"note":["Gesehen am 25.04.08"],"type":{"bibl":"periodical","media":"Online-Ressource"},"disp":"A unified Erdős-Pósa theorem for constrained cyclesCombinatorica","name":{"displayForm":["JBMS, János Bolyai Mathematical Society"]},"recId":"253721385","physDesc":[{"extent":"Online-Ressource"}],"id":{"zdb":["1458905-9"],"issn":["1439-6912"],"eki":["253721385"]},"title":[{"title_sort":"Combinatorica","title":"Combinatorica","subtitle":"an international journal on combinatorics and the theory of computing"}],"origin":[{"publisher":"Springer","dateIssuedDisp":"1981-","dateIssuedKey":"1981","publisherPlace":"Berlin ; Heidelberg"}]}],"name":{"displayForm":["Tony Huynh, Felix Joos, Paul Wollan"]},"language":["eng"],"note":["Online first 14 August 2018","Gesehen am 27.07.2022"],"person":[{"family":"Huynh","role":"aut","display":"Huynh, Tony","given":"Tony"},{"display":"Joos, Felix","given":"Felix","family":"Joos","role":"aut"},{"given":"Paul","display":"Wollan, Paul","family":"Wollan","role":"aut"}],"recId":"1810693233"} | ||
| SRT | |a HUYNHTONYJUNIFIEDERD2019 | ||