Multicolored forests in bipartite decompositions of graphs (Q1186126)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Multicolored forests in bipartite decompositions of graphs |
scientific article |
Statements
Multicolored forests in bipartite decompositions of graphs (English)
0 references
28 June 1992
0 references
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.
0 references
colouring
0 references
bipartite decomposition
0 references
spanning tree
0 references
forest
0 references
near-tree
0 references
near-forest
0 references
clique decompositions
0 references
matchings
0 references