Edge Colorings of Complete Multipartite Graphs Forbidding Rainbow Cycles
Authors:
- Auburn UniversityAUAuburn University
- Peter JohnsonPJPeter Johnson
Open Access
- 1 January 2017
- journal article
- Published by Georgia Southern University in Theory and Applications of Graphs
- Vol. 4 (2) , 1-9
Abstract
It is well known that if the edges of a finite simple connected graph on n vertices are colored so that no cycle is rainbow, then no more than n-1 colors can appear on the edges. In previous work it has been shown that the essentially different rainbow-cycle-forbidding edge colorings of Kn with n-1 colors appearing are in 1-1 correspondence with (can be encoded by) the (isomorphism classes of) full binary trees with n leafs. In the encoding, the natural Huffman labeling of each tree arising from the assignment of 1 to each leaf plays a role. Very recently it has been shown that a similar encoding holds for rainbow-cycle-forbidding edge colorings of Ka,b with a+b-1 colors appearing. In this case the binary trees are given Huffman labelings arising from certain assignments of (0,1) or (1,0) to the leafs. (Sibling leafs are not allowed to be assigned the same label.) In this paper we prove the analogous result for complete r-partite graphs, for r > 2.Keywords
This publication has 2 references indexed in Scilit:
- Edge Colorings of K(m,n) with m+n-1 Colors Which Forbid Rainbow CyclesTheory and Applications of Graphs, 2017
- Rainbow generalizations of Ramsey theory - a dynamic surveyTheory and Applications of Graphs, 2014