Coloring and Structure

着色和结构

• 批准号: 1001091
• 负责人: Maria Chudnovsky
• 金额: $ 17.65万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-15 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1001091&HistoricalAwards=false
• 关键词: Coloring; Structure

The PI proposes to work on three problems in graph theory that relate certain coloring properties of graphs with their structure. The first problem is a variant of Hadwiger's conjecture, due to Abu-Khzam and Langston, that says that for every non-negative integer t, every graph with chromatic number at least t immerses the complete graph of size t. The second problem is the well-known Erdos-Lovasz Tihany Conjecture. It states that for every graph G whose chromatic number, k, is strictly bigger than its chromatic number, and for every two integers s,t, both strictly bigger than 2, and adding up to k+1, there is a partition (S,T) of the vertex set of G, such the chromatic number of the subgraph of G induced by S is at least s, and the chromatic number of the subgraph of G induced by T is at least t. The PI plans to work on this conjecture for the class of claw-free graphs using a recent structure theorem. The last problem is a conjecture of Erdos and Sos that states that every graph with average degree bigger than k-1 contains every tree on k+1 vertices as a subgraph. Here the PI is especially interested in the variant of the conjecture where subgraph containment is replaced by minor containment.Graph coloring is one of the basic questions addressed in graph theory. The questions is: what is the smallest number of colors needed to color the vertices of a given graph, in such a way that no two adjacent vertices get the same color. There have been quite a few attempts to explain (from the point of view of the structure of the graph) why many colors are needed for some graphs, while only a few are necessary for others. One of the most famous conjectures in this direction is a well known conjecture of Hadwiger, that states that if a graph requires many colors, then it contains a certain substructure, called a "clique minor". This grant proposal is concerned with three conjectures in graph theory that connect coloring properties of graphs with certain structural properties. Two of the conjectures are quite well known, while the third one is a less well known variation of Hadwiger's conjecture. All three problems have been open for a while, and the PI proposes to work on a number of new cases and variations, where there is a better chance of success. As in every fundamental study, there is room for collaboration across all academic levels: there are special cases that can be investigated by graduate students or superior undergraduates. Those special cases can prove useful in suggesting novel proof strategies or leading to counterexamples.

PI建议研究图论中的三个问题，这些问题将图的某些着色性质与其结构联系起来。 第一个问题是Hadwiger猜想的一个变体，由Abu-Khzam和兰斯顿提出，即对于每个非负整数t，每个色数至少为t的图都浸入大小为t的完全图。第二个问题是著名的Erdos-Lovasz Tihany猜想。本文证明了：对任意一个图G，若其色数k严格大于其色数，且任意两个整数s，t均严格大于2，且之和为k+1，则G的顶点集存在一个划分（S，T），使得由S诱导的G的子图的色数至少为s，且G的由T诱导的子图的色数至少为t。PI计划使用最近的结构定理来研究无爪图类的这个猜想。最后一个问题是Erdos和Sos的一个猜想，即每个平均度大于k-1的图都包含k+1个顶点上的树作为子图。在这里PI特别感兴趣的是猜想的变体，其中子图包含被小包含取代。图着色是图论中的基本问题之一。问题是：用什么颜色来给给定图的顶点着色，使得没有两个相邻的顶点得到相同的颜色。已经有相当多的尝试来解释（从图的结构的角度来看）为什么一些图需要许多颜色，而另一些图只需要几种颜色。在这个方向上最著名的猜想之一是Hadwiger的一个著名猜想，该猜想指出，如果一个图需要许多颜色，那么它包含一定的子结构，称为“团子”。这项拨款建议是关于图论中的三个结构，这些结构将图的着色性质与某些结构性质联系起来。其中两个猜想是相当有名的，而第三个是一个不太知名的变化哈德维格猜想。所有这三个问题都已经公开了一段时间，PI建议研究一些新的案例和变体，这些案例和变体有更好的成功机会。 正如在每一项基础研究中一样，所有学术水平都有合作的空间：有些特殊情况可以由研究生或上级本科生进行研究。这些特殊情况可以证明在建议新的证明策略或导致反例有用。