混合图的边着色

Edge-coloring of Mixed Graph

著名学者Daniel Krlá.,Jan Kratochvlí,Heinz-Jürgen Voss等曾在其著名论文《Mixed hypergraphs with bound-ed degree:edge-coloring of mixed multigraphs》中提出任何一个混合超图均可一一对应地转化成一个最大度不超过3的混合超图,且它们的着色亦是一一对应的。因此,研究最大度为3的混合超图的着色问题具有一般性,是困难的;而研究最大度为1的混合超图的着色问题是平凡的;所以我们着力研究最大度为2的混合超图。而最大度为2的混合超图的点着色问题可以一一对应地转化为一个与其对应的混合多重图的边着色问题,因此,文章从特殊的混合多重图-混合图入手,着力研究混合图的边着色。

Daniel Kral, Jan Kratochvil and Heinz -- jurgen Voss conclude that one can construct a mixed hypergraph with maximum degree three whose proper colorings one--to--one correspond to the proper colorings of the original one. Those ones with maximum vertex degree one are trivial and those ones with maximum vertex degree three are not less general than all mixed hypergraphs and difficulty. Thus,we restrict our attention to mixed hypergraphs with maximum vertex degree two. Again, they propose that there is a mixed multigraph whose proper edge--colorings one--to--one correspond to the proper vertexcolorings of any mixed hypergraph. Since we are familier with the theory and methods of edge--colorings of graphs and multigraphs, we devote attentions to the edge--colorings study of mixed multigraphs, further studying and perfecting the coloring theory of mixed hypergraphs.