A Vizing-type theorem for matching forests |
| |
Authors: | Judith Keijsper |
| |
Institution: | Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, 5600 MB, Eindhoven, The Netherlands |
| |
Abstract: | A well-known Theorem of Vizing states that one can colour the edges of a graph by Δ+ colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and the maximum multiplicity of an edge in the graph. An analogue of this Theorem for directed graphs was proved by Frank. It states that one can colour the arcs of a digraph by Δ+ colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and the maximum multiplicity of an arc. We prove a common generalization of the above two theorems concerning the colouring of mixed graphs (these are graphs having both directed and undirected edges) in such a way that edges of the same colour form a matching forest. |
| |
Keywords: | Edge colouring Mixed graph Matching Branching |
本文献已被 ScienceDirect 等数据库收录! |
|