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
    0 references
    0 references
    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

    Identifiers