Edge decomposition of complete tripartite graphs

    Research output: Contribution to journalArticlepeer-review

    Abstract

    THE SPECIAL CHARACTERS IN THIS ABSTRACT CANNOT BE DISPLAYED CORRECTLY ON THIS PAGE. PLEASE REFER TO THE ABSTRACT ON THE PUBLISHER'S WEBSITE FOR AN ACCURATE DISPLAY. A graph H decomposes a graph G if and only if the edges of G can be partitioned into disjoint subsets each of which induces a graph isomorphic to H. Wilson (in: C.St.J.A. Nash-Williams, J. Sheehan (Eds.), Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975) showed, among other things, that for any graph H, there is an integer n such that H decomposes Kn, and Häggkvist (in: J. Siemons (Ed.), Surveys in Combinatories 1989, Invited papers for 12th British Combinatorial Conference, LMS Lecture Notes 141, Cambridge University Press, Cambridge, 1989, pp. 115–147) showed that for any bipartite H, there is an n such that H decomposes Kn,n. In this paper, we extend this result to tripartite graphs, by showing that for any tripartite graph H, there is an integer n such that H decomposes Kn,n,n.
    Original languageEnglish
    Pages (from-to)269-275
    Number of pages7
    JournalDiscrete Mathematics
    Volume272
    Issue number2-3
    DOIs
    Publication statusPublished - Nov 2003

    Keywords

    • Graph decomposition
    • Tripartite graph
    • Multipartite graph

    Fingerprint

    Dive into the research topics of 'Edge decomposition of complete tripartite graphs'. Together they form a unique fingerprint.

    Cite this