Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A Unified Erdős–Pósa Theorem for Constrained Cycles

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

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.

Moreover, our approach gives a unified framework for proving packing results for constrained cycles in graphs. For example, as immediate corollaries we recover the Erdős–Pósa property for cycles and S-cycles and the half-integral Erdős–Pósa property for odd cycles and odd S-cycles. Furthermore, we recover Reed's Escher-wall Theorem.

We also prove many new packing results as immediate corollaries. For example, we show that the half-integral Erdős–Pósa property holds for cycles not homologous to zero, odd cycles not homologous to zero, and S-cycles not homologous to zero. Moreover, the (full) Erdős–Pósa property holds for S1-S2-cycles and cycles not homologous to zero on an orientable surface. Finally, we also describe the canonical obstructions to the Erdős–Pósa property for cycles not homologous to zero and for odd S-cycles.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E. Birmelé, J.A. Bondy and B. Reed: The Erdős–Pósa property for long circuits, Combinatorica 27 (2007), 135–145.

    Article  MathSciNet  MATH  Google Scholar 

  2. H. Bruhn, F. Joos and O. Schaudt: Long cycles through prescribed vertices have the Erdős–Pósa property, to appear in J. Graph Theory.

  3. M. Chudnovsky, J. Geelen, B. Gerards, L. Goddyn, M. Lohman and P. Seymour: Non-zero A-paths in group-labelled graphs, Combinatorica 26 (2006), 521–532.

    Article  MathSciNet  MATH  Google Scholar 

  4. R. P. Dilworth: A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161–166.

    Article  MathSciNet  MATH  Google Scholar 

  5. P. Erdős and L. Pósa: On the maximal number of disjoint circuits of a graph, Publ. Math. Debrecen 9 (1962), 3–12.

    MathSciNet  MATH  Google Scholar 

  6. P. Erdős and G. Szekeres: A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.

    MathSciNet  MATH  Google Scholar 

  7. S. Fiorini and A. Herinckx: A tighter Erdős–Pósa function for long cycles, J. Graph Theory 77 (2013), 111–116.

    Article  MATH  Google Scholar 

  8. J. Geelen and B. Gerards: Excluding a group-labelled graph, J. Combin. Theory Ser. B 99 (2009), 247–253.

    Article  MathSciNet  MATH  Google Scholar 

  9. J. Geelen, B. Gerards, B. Reed, P. Seymour and A. Vetta: On the odd-minor variant of Hadwiger's conjecture, J. Combin. Theory (Series B) 99 (2009), 20–29.

    Article  MathSciNet  MATH  Google Scholar 

  10. T. Huynh: The linkage problem for group-labelled graphs, PhD thesis, University of Waterloo, 2009.

    Google Scholar 

  11. N. Kakimura, K. Kawarabayashi and D. Marx: Packing cycles through prescribed vertices, J. Combin. Theory Ser. B 101 (2011), 378–381.

    Article  MathSciNet  MATH  Google Scholar 

  12. K. Kawarabayashi and N. Kakimura: Half-integral packing of odd cycles through prescribed vertices, Combinatorica 33 (2014), 549–572.

    MathSciNet  MATH  Google Scholar 

  13. K. Kawarabayashi, R. Thomas and P. Wollan: A new proof of the Flat Wall Theorem, J. Combin. Theory Ser. B 129 (2018), 204–238.

    Article  MathSciNet  MATH  Google Scholar 

  14. D. Lokshtanov, M. S. Ramanujan and S. Saurabh: The half-integral Erdős–Pósa property for non-null cycles, arXiv:1703.02866, 2017.

    Google Scholar 

  15. M. Pontecorvi and P. Wollan: Disjoint cycles intersecting a set of vertices, J. Combin. Theory (Series B) 102 (2012), 1134–1141.

    Article  MathSciNet  MATH  Google Scholar 

  16. B. Reed: Mangoes and blueberries, Combinatorica 19 (1999), 267–296.

    Article  MathSciNet  MATH  Google Scholar 

  17. N. Robertson and P. Seymour: Graph minors. X. Obstructions to tree-decomposition, J. Combin. Theory Ser. B 52 (1991), 153–190.

    Article  MathSciNet  MATH  Google Scholar 

  18. N. Robertson and P. Seymour: Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B 63 (1995), 65–110.

    Article  MathSciNet  MATH  Google Scholar 

  19. C. Thomassen: On the presence of disjoint subgraphs of a specified type, J. Graph Theory 12 (1988), 101–111.

    Article  MathSciNet  MATH  Google Scholar 

  20. P. Wollan: Packing cycles with modularity constraints, Combinatorica 31 (2011), 95–126.

    Article  MathSciNet  MATH  Google Scholar 

  21. T. Zaslavsky: Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), 32–52.

    Article  MathSciNet  MATH  Google Scholar 

  22. T. Zaslavsky: Biased graphs. II. The three matroids, J. Combin. Theory Ser. B 51 (1991), 46–72.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Département de Mathématique, Université Libre de Bruxelles, Bruxelles, Belgium

    Tony Huynh

  2. Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany

    Felix Joos

  3. Department of Computer Science, University of Rome, Rome, Italy

    Paul Wollan

Authors
  1. Tony Huynh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Felix Joos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Paul Wollan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tony Huynh.

Additional information

This research is supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC Grant Agreement no. 279558.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Huynh, T., Joos, F. & Wollan, P. A Unified Erdős–Pósa Theorem for Constrained Cycles. Combinatorica 39, 91–133 (2019). https://doi.org/10.1007/s00493-017-3683-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-017-3683-z

Mathematics Subject Classification (2000)

Search

Navigation