Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Multicolored isomorp ...
Article

Multicolored isomorphic spanning trees in complete graphs

Gregory Constantine (1)
(1) Department of Mathematics [Pittsburgh]
Download article
Open on HAL
Imported on
March 26, 2015
Published on
January 1, 2002
Last modified on
March 31, 2025
Volume 5
vol. 5
DOI
10.46298/dmtcs.306
License
https://about.hal.science/hal-authorisation-v1
Indicators
730
Views
605
Downloads

Multicolored isomorphic spanning trees in complete graphs

Gregory Constantine (1)
(1) Department of Mathematics [Pittsburgh]
Abstract
Can a complete graph on an even number n (>4) of vertices be properly edge-colored with n-1 colors in such a way that the edges can be partitioned into edge disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n-1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two, or five times a power of two.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Orthogonal Latin squares
  • colorful matching
  • multicolored tree
Cited by

Source: OpenCitations

  • Linearly many rainbow trees in properly edge-coloured complete graphs

    Journal of Combinatorial Theory Series B

    Authors : Alexey Pokrovskiy ORCID, Benny Sudakov ORCID

    Journal reference : Volume 132, 2018, pp. 134-156

    DOI : 10.1016/j.jctb.2018.03.005
  • Decompositions into spanning rainbow structures

    arXiv (Cornell University)

    Authors : Richard Montgomery ORCID, Alexey Pokrovskiy ORCID, Benjamin Sudakov

    Journal reference : Volume 119, 2019, pp. 899-959

    DOI : 10.1112/plms.12245
  • Rainbow structures in locally bounded colorings of graphs

    Random Structures and Algorithms

    Authors : Jaehoon Kim ORCID, Daniela Kühn ORCID, Andrey Kupavskii ORCID, Deryk Osthus ORCID

    Journal reference : Volume 56, 2020, pp. 1171-1204

    DOI : 10.1002/rsa.20902
  • Quaternionic 1-Factorizations and Complete Sets of Rainbow Spanning Trees

    IRIS UNIMORE (University of Modena and Reggio Emilia)

    Authors : Gloria Rinaldi ORCID

    Journal reference : Volume 39, 2023, pp.

    DOI : 10.1007/s00373-023-02610-6
  • Edge-disjoint rainbow trees in properly coloured complete graphs

    UCL Discovery (University College London)

    Authors : Alexey Pokrovskiy ORCID, Benny Sudakov ORCID

    Journal reference : Volume 61, 2017, pp. 995-1001

    DOI : 10.1016/j.endm.2017.07.064
  • Multicolored trees in complete graphs

    Journal of Graph Theory

    Authors : S. Akbari ORCID, A. Alipour ORCID

    Journal reference : Volume 54, 2006, pp. 221-232

    DOI : 10.1002/jgt.20204
  • Decompositions into isomorphic rainbow spanning trees

    arXiv (Cornell University)

    Authors : Stefan Glock, Daniela Kühn ORCID, Richard Montgomery ORCID, Deryk Osthus ORCID

    Journal reference : Volume 146, 2020, pp. 439-484

    DOI : 10.1016/j.jctb.2020.03.002
  • Rainbow spanning trees in properly coloured complete graphs

    arXiv (Cornell University)

    Authors : József Balogh, Hong Liu ORCID, Richard Montgomery ORCID

    Journal reference : Volume 247, 2018, pp. 97-101

    DOI : 10.1016/j.dam.2018.03.066
  • Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees

    SIAM Journal on Discrete Mathematics

    Authors : Linyuan Lu ORCID, Zhiyu Wang ORCID

    Journal reference : Volume 34, 2020, pp. 2346-2362

    DOI : 10.1137/19m1299876
  • Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations

    IRIS UNIMORE (University of Modena and Reggio Emilia)

    Authors : G. Mazzuoccolo ORCID, G. Rinaldi ORCID

    Journal reference : Volume 342, 2018, pp. 1006-1016

    DOI : 10.1016/j.disc.2018.11.026
Preview
Loading PDF preview...