×

zbMATH — the first resource for mathematics

Group colorings of complete bipartite graphs and bounds for Häggkvist numbers. (Russian. English summary) Zbl 0672.05032
The paper concerns matchings in graphs. Let Q(n,G) be the set of all partitions of the edge set of a graph G into classes which are matchings of G. If \(q\in Q(n,G)\), then L(q) (or \(\ell (q))\) is the length of the longest (or shortest respectively) cycle whose edges belong mutually to two classes of q. By L(n,G) the minimum of L(q) and by \(\ell (n,G)\) the maximum of \(\ell (q)\) is denoted, both taken over all \(q\in Q(n,G)\). Some assertions concerning the numbers L(n,G) and \(\ell (n,G)\) are proved. Their connection to the loop theory (“loop” in the algebraic sense) is shown. These numbers are related to a certain problem suggested by R. Häggkvist.
Reviewer: B.Zelinka

MSC:
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: EuDML