Colorings and List Colorings: Contrasts and Similarities

一个(超)图的(n个普通的)真染色是将颜色分配给这个超图的顶点，使得没有边成为单色的。超图的色数是用于适当着色的最小颜色数。在许多应用程序中，只使用几种颜色找到合适的颜色可能会很有用。颜色的分配可以模拟资源分配；边缘表示资源使用中的冲突。应用领域包括调度、数据库访问、计算机寄存器分配、数据集群、印制电路的计算机辅助设计、位置游戏、DNA测序等。更通用的列表着色模型允许限制每个顶点可用的颜色。将为每个顶点指定一个可用颜色列表。每个顶点的颜色必须从其列表中选择，但边施加的约束仍必须由所选颜色满足。列表着色可以用来对子图的着色扩展等问题进行建模。超图的表色数是最小的k，使得只要所有列表的大小至少为k，就有可能从所分配的列表中选择合适的着色。具有k种颜色的适当着色可以被认为是具有相同(大小为k)的所有顶点列表的列表着色。因此，一个超图的表色数总是至少是这个色数。尽管人们可能认为列表着色最困难的情况是所有列表都相同(给颜色带来更多冲突)，但情况并不总是如此。Viing和Erdos，Rubin，and Taylor给出了2个列表色数任意大的可染图的例子。另一方面，在一些(超)图类中，列表色数的行为类似于(普通)色数.本课题的主要目的是探索许多关于普通着色的结果的列表着色的类比.问题是在什么条件下，相关的列表着色和着色问题有类似的界限。着色参数的上界可以导致高效的算法；下界对可以实现的内容施加限制。一个问题是，列表色数何时实际上等于色数。另一个问题是需要多少条边才能形成一个具有给定色数的(超)图，这取决于各种附加条件；这里还将探讨列表着色类比。对于利用特殊类型几何对象的交集得到的图类，求出了关于两两相邻顶点的最大数目的(列表)色数的界。许多着色问题都有使用列表的相似之处，本项目将开始探索其中的许多列表着色问题。例如，许多广义着色参数在重要的图类上具有有界值，例如平面图(那些嵌入平面中没有边交叉的图)。当为顶点分配有界大小的颜色列表时，这样的颜色是否仍然存在？大部分工作计划与道格拉斯·B·韦斯特(伊利诺伊大学香槟分校)共同完成

A(n ordinary) proper coloring of a (hyper)graph is an assignment of colors to the vertices of this hypergraph in such a way that no edge becomes monochromatic. The chromatic number of a hypergraph is the minimum number of colors used in a proper coloring. Finding proper colorings using only few colors can be useful in many applications. The assignment of colors can model resource allocation; the edges represent conflicts in usage of resources. Areas of application include scheduling, database access, assignment of computer registers, data clustering, computer aided design of printed circuits, positional games, DNA sequencing, etc. The more general model of list coloring allows to restrict the colors available for each vertex. Each vertex is assigned a list of available colors. The color for each vertex must be chosen from its list, but the constraints imposed by edges must still be satisfied by the chosen coloring. List coloring can be used to model problems such as extension of colorings of subgraphs. The list chromatic number of the hypergraph is the minimum k such that whenever all lists have size at least k, it is possible to choose a proper coloring from the assigned lists. A proper coloring with k colors can be considered as a list coloring with all the lists of vertices being the same (of size k). Thus, the list chromatic number of a hypergraph always is at least the chromatic number. Although one might think that the most difficult case of list coloring is when all the lists are the same (giving more conflicts for colors), this is not always the case. Vizing and Erdos, Rubin, and Taylor gave examples of 2 colorable graphs with arbitrarily large list chromatic number. On the other hand, in some classes of (hyper)graphs the list chromatic number behaves similarly to the (ordinary) chromatic number.The main thrust of this project is to explore the analogs for list coloring of many results about ordinary coloring. The issue is under what conditions there are similar bounds for related list coloring and coloring problems. Upper bounds on coloring parameters can lead to efficient algorithms; lower bounds impose limits on what can be accomplished. One question is when the list chromatic number actually equals the chromatic number. Another is how many edges are needed to form a (hyper)graph with a given chromatic number, subject to various additional conditions; here a list coloring analogue will also be explored. For classes of graphs obtained using intersections of geometric objects of special types, bounds on (list) chromatic number in terms of the maximum number of pairwise adjacent vertices are sought. Many coloring problems have analogs using lists, and this project will begin the exploration of many of these list coloring problems. For example, many generalized coloring parameters have bounded values on important classes of graphs such as the planar graphs (those that embed in the plane without edge crossings). Do such colorings still exist when the vertices are assigned color lists of bounded size? Most of the work is planned to be done jointly with Douglas B. West (University of Illinois at Urbana-Champaign)