Coloring and Structure

PI建议致力于图论中的三个问题，这三个问题将图的某些着色性质与其结构联系起来。第一个问题是Hadwiger猜想的变形，这是由Abu-Khzam和Langston提出的，即对每个非负整数t，每个色数至少为t的图都浸没了大小为t的完全图。第二个问题是著名的Erdos-Lovasz Tihany猜想。对图G的色数k严格大于其色数，且对每两个严格大于2且加到k1的整数S，t，都有G的点集的一个划分(S，T)，使得由S诱导的G的子图的色数至少为S，且由T诱导的G的子图的色数至少为t。PI计划利用最近的结构定理对这类无爪图进行这一猜想。最后一个问题是Erdos和SOS的一个猜想，即每个平均度大于k-1的图都包含k个顶点上的每棵树作为一个子图。在这里，PI特别感兴趣的是猜想的变体，其中子图包含被次包含取代。图着色是图论中讨论的基本问题之一。问题是：要给给定图的顶点上色，使相邻的两个顶点没有相同的颜色，所需的最小颜色数是多少。人们曾多次尝试(从图表结构的角度)解释为什么有些图表需要很多颜色，而另一些图表只需要几种颜色。在这个方向上最著名的猜想之一是Hadwiger的一个众所周知的猜想，该猜想指出，如果一个图需要许多颜色，那么它包含一个特定的子结构，称为“集团次要”。这项拨款建议涉及图论中的三个猜想，它们将图的着色性质与某些结构性质联系起来。其中两个猜想是众所周知的，而第三个猜想是Hadwiger猜想的一个不太为人所知的变体。这三个问题都已经解决了一段时间，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.