Multicolored forests in bipartite decompositions of graphs (Q1186126)

The paper studies bipartite decompositions of graphs. A bipartite decomposition of a graph is a colouring of edges of \(G\) such that each colour class is the set of all edges of a complete bipartite subgraph of \(G\). Theorem 1 states that in any bipartite decomposition of \(K_ n\) there is a spanning tree of \(K_ n\), no two of whose edges have the same colour. This is a strengthening of a conjecture by D. de Caen. A more general theorem is Theorem 2 stating that if \(G\) is a graph with \(p\) positive and \(q\) negative eigenvalues, then in any bipartite decomposition of \(G\) there is a forest with \(\max\{p,q\}\) edges, no two of which have the same colour. Further theorems bring similar results concerning near-trees and near-forests. A near-tree is an unicyclic graph having a circuit of odd length, a near-forest is a graph, all of whose connected components are near-trees. Also clique decompositions and matchings are studied.