论文标题
全球结构条件下的图形着色
Graph colorings under global structural conditions
论文作者
论文摘要
十多年前的2008年，图理论中出现了一种新的图形着色，它是图形的{\ it彩虹连接着色}，然后是图形色素的其他一些新概念，例如{\ it正确连接着色，单色连接着色和冲突的无冲突连接着色}。在我们始终如一的研究的大约十年中，我们发现这些新的图形颜色的新概念实际上与经典的图形色素有很大不同。这些图的这些{\ it彩色连接着色}是全新的着色，它们需要照顾颜色下图的全球结构属性（例如连接性）；图形的传统着色是颜色下的，仅处理图形的局部结构特性（相邻的顶点或边缘）。经典着色和新的彩色连接着色都可以产生所谓的色数。我们将彩色连接数字称为{\ it全局色数}，而经典或传统的色度为{\ it local彩色数}。本文旨在阐明彩色连接着色和传统着色之间的差异，最后提出了保留了彩色图的全球结构属性和全局色数的新概念。
More than ten years ago in 2008, a new kind of graph coloring appeared in graph theory, which is the {\it rainbow connection coloring} of graphs, and then followed by some other new concepts of graph colorings, such as {\it proper connection coloring, monochromatic connection coloring, and conflict-free connection coloring} of graphs. In about ten years of our consistent study, we found that these new concepts of graph colorings are actually quite different from the classic graph colorings. These {\it colored connection colorings} of graphs are brand-new colorings and they need to take care of global structural properties (for example, connectivity) of a graph under the colorings; while the traditional colorings of graphs are colorings under which only local structural properties (adjacent vertices or edges) of a graph are taken care of. Both classic colorings and the new colored connection colorings can produce the so-called chromatic numbers. We call the colored connection numbers the {\it global chromatic numbers}, and the classic or traditional chromatic numbers the {\it local chromatic numbers}. This paper intends to clarify the difference between the colored connection colorings and the traditional colorings, and finally to propose the new concepts of global colorings under which global structural properties of the colored graph are kept, and the global chromatic numbers.
