Coloring and Structure

PI计划研究图论中的三个问题，将图的某些着色性质与其结构联系起来。第一个问题是哈维格猜想的一个变体，由阿布-赫扎姆和兰斯顿提出，它说对于每一个非负整数t，每一个色数至少为t的图都包含着大小为t的完全图。第二个问题是著名的Erdos-Lovasz Tihany猜想。州,每一个图G的彩色数字,k,是严格大于它的色号,每两个整数,t,严格大于2,并添加到k + 1,有一个分区(s, t) G的顶点集,这样引起的G的子图的色数至少是年代,和G的子图的色数由t至少是t。π计划工作在这个猜想claw-free图的类使用最近的一个结构定理。最后一个问题是Erdos和Sos的一个猜想，即每个平均度大于k-1的图都包含k+1个顶点的所有树作为子图。这里PI特别感兴趣的是猜想的变体，其中子图包含被次要包含所取代。图的着色是图论研究的基本问题之一。问题是：为给定图的顶点上色所需的最小颜色数是多少，以使相邻的两个顶点的颜色不相同。已经有相当多的尝试来解释（从图表结构的角度）为什么有些图表需要很多颜色，而有些图表只需要几种颜色。在这个方向上最著名的猜想之一是哈德维格的一个众所周知的猜想，该猜想指出，如果一个图需要许多颜色，那么它包含一个特定的子结构，称为“小团”。本申请涉及图论中的三个猜想，它们将图的着色性质与某些结构性质联系起来。其中两个猜想是众所周知的，而第三个猜想是哈维格猜想的一个不太为人所知的变体。这三个问题已经存在了一段时间，PI建议研究一些新的案例和变体，在这些案例和变体中，成功的机会更大。就像在所有基础研究中一样，所有学术水平的合作都有空间：有一些特殊的案例可以由研究生或更优秀的本科生来研究。这些特殊情况可以证明在提出新的证明策略或导致反例方面是有用的。

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.