Colorings and List Colorings: Contrasts and Similarities

一个（超）图的（n普通）真染色是指给这个超图的顶点分配颜色，使得没有边成为单色的。 一个超图的色数是一个正常染色所用的最小颜色数。 在许多应用中，仅使用少数颜色来找到适当的着色是有用的。 颜色的分配可以模拟资源分配;边缘表示资源使用中的冲突。 应用领域包括调度，数据库访问，计算机寄存器分配，数据聚类，印刷电路的计算机辅助设计，位置游戏，DNA测序等。 每个顶点都被指定了一个可用颜色的列表。 每个顶点的颜色必须从它的列表中选择，但是所选择的着色仍然必须满足边所施加的约束。 列表着色可以用来模拟诸如子图着色扩展之类的问题。 超图的列表色数是最小的k，使得只要所有列表的大小至少为k，就可以从分配的列表中选择适当的着色。一个有k种颜色的正常染色可以被认为是一个所有顶点列表都相同（大小为k）的列表染色。 因此，超图的列表色数总是至少为色数。 虽然人们可能认为列表着色最困难的情况是当所有列表都相同时（给颜色带来更多冲突），但情况并非总是如此。 Vizing和Erdos，Rubin和Taylor给出了具有任意大列表色数的2个可着色图的例子。 另一方面，在某些类（超）图中，列表色数的性质与（普通）色数的性质相似。 问题是在什么条件下有类似的界限相关的列表着色和着色问题。 着色参数的上界可以导致有效的算法;下界对可以完成的工作施加限制。 一个问题是当列表色数实际上等于色数时。 另一个是需要多少条边来形成一个给定色数的（超）图，受各种附加条件的影响;这里还将探讨列表着色模拟。 对于一类特殊类型的几何对象的交集所得到的图，寻求了关于最大成对相邻顶点数的色数的界。 许多着色问题都类似于使用列表，这个项目将开始探索许多这样的列表着色问题。 例如，许多广义着色参数在重要的图类上具有有界值，例如平面图（嵌入在平面中而没有边交叉的图）。 当顶点被分配了有限大小的颜色列表时，这样的着色仍然存在吗？ 大部分工作计划与道格拉斯B联合完成。伊利诺伊大学香槟分校（University of Illinois at Urbana-Champaign）

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)