Coloring and Structure

Columbia University, New York NY

Investigators

Abstract

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.