Skip to main content
SpringerLink
Log in

A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors.

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

Similar content being viewed by others

References

  1. Albert, M., Frieze, A., Reed, B.: Multicoloured Hamilton cycles. Electron. J. Comb. 2, ♯R10 (1995)

  2. Alon, N., Brualdi, R.A., Shader, B.L.: Multicolored forests in bipartite decompositions of graphs. J. Comb. Theory Ser. B 53, 143–148 (1991)

    Google Scholar 

  3. Brualdi, R.A., Hollingsworth, S.: Multicolored trees in complete graphs. J. Comb. Theory Ser. B 68, 310–313 (1996)

    Google Scholar 

  4. Brualdi, R.A., Hollingsworth, S.: Multicolored forests in complete bipartite graphs. Discrete Math. 240, 239–245 (2001)

    Google Scholar 

  5. Erdös, P., Tuza, Z.: Rainbow Hamiltonian paths and canonically colored subgraphs in infinite complete graphs. Math. Pannonica 1(1), 5–13 (1990)

    Google Scholar 

  6. Faudree, R.J., Gyárfás, A., Lesniak, L., Schelp, R.H.: Rainbow coloring the cube. J. Graph Theory 17(5), 607–612 (1993)

    Google Scholar 

  7. Fu, H-L., Woolbright, D.E.: On the existence of rainbows in 1-factorizations of K2n. J. Comb. Des. 6, 1–20 (1998)

    Google Scholar 

  8. Graham, R.L., Pollak, H.O.: On the addressing problem for loop switching. Bell Syst. Teck. J. 50, 2495–2519 (1971)

    Google Scholar 

  9. Graham, R.L., Pollak, H.O.: On embedding graphs in squashed cubes. Lecture Notes in Mathematics, Vol.303, Springer-Verlag, New York/Berlin/Heidelberg, 99–110 (1973)

  10. Kaneko, A., Kano, M., Suzuki, K.: Three edge-disjoint Multicolored Spanning Trees in Complete Graphs. preprint (2002)

  11. Peck, G.W.: A new proof of a theorem of Graham and Pollak. Discrete Math. 49, 327–328 (1984)

    Google Scholar 

  12. Rödl, V., Tuza, Z.: Rainbow subgraphs in properly edge-colored graphs. Random Struct. Algorithms 3(2), 175–182 (1992)

    Google Scholar 

  13. Schiermeyer, I.: Rainbow colourings. Not. S. Afr. Math. Soc. 34(1), 51–59 (2003)

  14. Schiermeyer, I.: Rainbow numbers for matchings and complete graphs. Discrete Math. 286, 157–162 (2004)

    Google Scholar 

  15. Shor, P.W.: A lower bound for the length of a partial transversal in a Latin square. J. Comb. Theory Ser. A 33, 1–8 (1982)

    Google Scholar 

  16. Tverberg, H.: On the decomposition of K n into complete bipartite graphs. J. Graph Theory 6(4), 493–494 (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Information Sciences, Ibaraki University, Hitachi, Ibaraki, 316-8511, Japan

    Kazuhiro Suzuki

Authors
  1. Kazuhiro Suzuki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kazuhiro Suzuki.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Suzuki, K. A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph. Graphs and Combinatorics 22, 261–269 (2006). https://doi.org/10.1007/s00373-006-0662-3

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-006-0662-3

Keywords

Search

Navigation