A CONSTRUCTIVE PROOF OF VIZINGS THEOREM

作     者：MISRA, J GRIES, D 

作者机构：UNIV TEXASDEPT COMP SCIAUSTINTX 78712 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：1992年第41卷第3期

页      面：131-133页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Correspondence to: Professor D. Gries  Department of Computer Science  Cornell University  4115 Upson Hall  Ithaca  NY 14853-7501  USA. * This work was done while the second author was on sabbatic at Austin. He has returned to the Computer Science Department  Cornell University 

主　　题：ANALYSIS OF ALGORITHMS PROGRAM CORRECTNESS GRAPH ALGORITHMS GRAPH COLORING 

摘      要：Finite graphs with no self-loops and no multiple edges are considered. Each edge of the graph has a color or is uncolored. A graph is valid if no 2 edges incident on a vertex have the same color. A proof is presented of Vizing s Theorem, which states that, in a graph of maximum degree less than N, all edges can be colored using N colors so that the graph is valid. The proof consists of showing how to color an arbitrary uncolored edge of a valid graph, which may require changing the colors of already-colored edges to maintain validity. This procedure can be repeated until all edges are colored.