Skip to main content
SpringerLink
Log in

Trees, Paths, Stars, Caterpillars and Spiders

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

For any \(k \ge 2\), deciding whether the linear arboricity, star arboricity, caterpillar arboricity, spider arboricity, track number, unit track number, and subchromatic index, respectively, of a bipartite graph are at most k are all NP-complete.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Akiyama, J., Exoo, G., Harary, F.: Covering and packing in graphs III: cyclic and acyclic invariants. Math. Slovoca 30, 405–417 (1980)

    MathSciNet  MATH  Google Scholar 

  2. Albertson, M.O., Jamison, R.E., Hedetniemi, S.T., Locke, S.C.: The subchromatic number of a graph. Discret. Math. 74, 33–49 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  3. Alon, N.: The linear arboricity of graphs. Isr. J. Math. 62, 311–325 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  4. Alon, N., Teague, V.J., Wormald, N.C.: Linear arboricity and linear \(k\)-arboricity of regular graphs. Graphs Comb. 17, 11–16 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  5. Cai, L., Ellis, J.A.: NP-completeness of edge-colouring some restricted graphs. Discret. Appl. Math. 30, 15–27 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cameron, P.J.: Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, Cambridge (1994)

    MATH  Google Scholar 

  7. Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in \(O(E\log D)\) time. Combinatorica 21, 5–12 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  8. Cygan, M., Hou, J., Kowalik, Ł., Lužar, B., Wu, J.: A planar linear arboricity conjecture. J. Graph Theory 69, 403–425 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  9. Emden-Weinert, T., Hougardy, S., Kreuter, B.: Uniquely colourable graphs and the hardness of colouring graphs of large girth. Comb. Probab. Comput. 7, 375–386 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  10. Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Comb. 11, R46 (2004)

    MathSciNet  MATH  Google Scholar 

  11. Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcolorings: complexity and algorithms. SIAM J. Discret. Math. 16, 635–650 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fiala, J., Le, V.B.: The subchromatic index of graphs. Tatra Mt. Math. Publ. 36, 129–146 (2007)

    MathSciNet  MATH  Google Scholar 

  13. Gabow, H.N., Westermann, H.H.: Forests, frames, and games: algorithms for matroid sums and applications. Algorithmica 7, 465–497 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gimbel, J., Hartman, C.: Subcolorings and the subchromatic number of a graph. Discret. Math. 272, 139–154 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gonçalves, D.: Caterpillar arboricity of planar graphs. Discret. Math. 307, 2112–2121 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Gonçalves, D., Ochem, P.: On star and caterpillar arboricity. Discret. Math. 309, 3694–3702 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hakimi, S.L., Mitchem, J., Schmeichel, E.: Star arboricity of graphs. Discret. Math. 149, 93–98 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  18. Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10, 718–720 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  19. Jiang, M.: Recognizing \(d\)-interval graphs and \(d\)-track interval graphs. Algorithmica 66, 541–563 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  20. Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. Journal of Algorithms 19, 104–115 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  21. Leven, D., Galil, Z.: NP completeness of finding the chromatic index of regular graphs. J. Algorithms 4, 35–44 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  22. Lovász, L.: Coverings and colorings of hypergraphs. In: Proceedings of the 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, pp. 3–12. Utilitas Mathematica Publishing, Winnipeg (1973)

  23. Maffray, F., Preissmann, M.: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs. Discret. Math. 162, 313–317 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  24. Nash-Williams, C.StJ A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. 39, 12 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  25. Peroche, B.: Complexité de l’arboricité linéaire d’un graphe. RAIRO Recherche Operationelle 16, 125–129 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  26. Shermer, T.C.: On rectangle visibility graphs III: external visibility and complexity. In: Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG’96), pp. 234–239 (1996)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Utah State University, Logan, UT, 84322-4205, USA

    Minghui Jiang

Authors
  1. Minghui Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Minghui Jiang.

Additional information

A preliminary version appeared in Proceedings of the 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2015).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiang, M. Trees, Paths, Stars, Caterpillars and Spiders. Algorithmica 80, 1964–1982 (2018). https://doi.org/10.1007/s00453-016-0237-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0237-5

Keywords

Search

Navigation