首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 Δ+greek small letter alpha colours, such that edges of the same colour form a matching. Here, Δ denotes the maximum degree of a vertex, and greek small letter alpha 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 Δ+greek small letter alpha colours, such that arcs of the same colour form a branching. For a digraph, Δ denotes the maximum indegree of a vertex, and greek small letter alpha 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号