Colorings and List Colorings: Contrasts and Similarities

着色和列表着色：对比和相似之处

• 批准号: 0099608
• 负责人: Alexandr Kostochka
• 金额: $ 10.32万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0099608&HistoricalAwards=false
• 关键词: Colorings; List; Contrasts; Similarities

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)

（超）图的（n普通）适当着色是对该超图的顶点进行颜色分配，使任何边都不会变成单色。超图的色数是在适当着色中使用的最小颜色数。在许多应用中，仅使用少数几种颜色就可以找到合适的颜色。颜色的分配可以模拟资源的分配；边表示资源使用上的冲突。应用领域包括调度、数据库访问、计算机寄存器分配、数据聚类、印刷电路的计算机辅助设计、位置游戏、DNA测序等。更一般的列表着色模型允许限制每个顶点可用的颜色。每个顶点被分配一个可用颜色列表。每个顶点的颜色必须从其列表中选择，但是所选的颜色仍然必须满足边所施加的约束。列表着色可用于对子图着色的扩展等问题进行建模。超图的列表色数是最小k，使得当所有列表的大小至少为k时，可以从指定的列表中选择适当的着色。k种颜色的适当着色可以被认为是所有顶点列表都相同（大小为k）的列表着色。因此，超图的表色数总是至少为色数。尽管有人可能认为列表着色最困难的情况是当所有列表都相同时（给颜色带来更多冲突），但情况并非总是如此。Vizing和Erdos， Rubin和Taylor给出了任意大列表色数的2个可色图的例子。另一方面，在（超）图的某些类中，表色数的行为类似于（普通）色数。本项目的主要目的是探索关于普通着色的许多结果的列表着色的类似物。问题是在什么条件下相关的列表着色和着色问题有相似的界限。着色参数的上界可以产生高效的算法；下限限制了可以完成的事情。一个问题是什么时候列表色数等于色数。另一个是需要多少条边来形成一个给定色数的（超）图，受制于各种附加条件；这里，我们还将探讨列表着色模拟。对于由特殊类型几何对象的交点得到的图类，求色数的界以成对相邻顶点的最大数目表示。许多着色问题都有使用列表的类似物，本项目将开始探索许多这些列表着色问题。例如，许多广义着色参数在重要的图类上具有有界值，例如平面图（那些嵌入在平面上而没有边交叉的图）。当顶点被分配了有限大小的颜色列表时，这种颜色是否仍然存在？大部分工作计划与Douglas B. West（伊利诺伊大学厄巴纳-香槟分校）共同完成。