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.
This project focused on three important problems in fundamental graph theory: the Erdos---Hajnal Conjecture, and Erdos---Lovasz Tihany Conjecture, and the Abu---Khzam-Langston Conjecture. Progress was made on all three problems. As is common in fundamental research, work on a particular question opened up a number of new directions that led to further advances in the field. On the Erdos---Hajnal Conjecture the PI, with her student and a collaborator, were able to construct an infinite family of graphs satisfying (an equivalent version of) the conjecture. Prior to that, only sporadic examples were known. Lead by attempts to make further progress on the conjecture, the PI and collaborators discovered a number of new general theorems on structure of graphs with certain substructures forbidden, once again advancing the current frontier of knowledge from sporadic examples to infinite families. Progress was also made on the Erdos-Lovasz Tihany Conjecture: the PI with a student and a former student were able to solve a new special case of the problem. Motivated initially by the Abu-Khzam---Langston Conjecture, the PI and collaborators were able to develop a new theory of "tournament immersion". This is a general theory dealing with a certain containment relation in an important family of graphs. As a result, a number of long-standing algorithmic problems for this class of graphs were resolved. The project also has a number of broader impacts. The PI has given lectures on results obtained under this award to both undergraduate and high school students. She taught a course at Columbia that relied heavily on outcomes of the project; she also organizes the Columbia Discrete Mathematics Semianar, that is attended, among others, by faculty members from a number of local non-PhD-granting institutions. Due to her location at the Columbia Engineering School, the PI is in an ideal position to engage in interdisciplinary research. She has collaborated with colleagues from Computer Science and Electrical Engineering on topics related to the current project.
