Structure, Colouring, and Flows in Graphs

点击翻译按钮获取中文摘要

In discrete mathematics, a graph is a set of points, some of which may be joined by lines. Graphs are useful models for chemical structures, electrical grids, the internet, transportation maps, and many other objects -- anything that can be viewed as a network is, abstractly, a graph. Real world problems involving such networks benefit from the theorems, algorithms, and insight of graph theory. The PI is most interested in graph problems involving structure, coloring, and related notions -- especially problems which connect coloring and structure. This project in particular focuses on four sub-projects involving immersion, edge-coloring, and flows.The first two sub-projects are both motivated by an immersion-analog of Hadwiger's Conjecture (the Abu-Khzam--Langston Conjecture), which links coloring and immersion. One sub-project seeks to find exact structural characterizations of graphs without specific immersions; the other seeks to better understand how immersions (and colorings) are affected when creating new graphs from old. A second conjecture involving coloring and structure that interests the PI greatly is the Goldberg-Seymour Conjecture on chromatic index. The PI plans to work to improve the method of Tashkinov trees -- the dominant technique used for approximation results towards the conjecture. The final sub-project concerns flows, and is somewhat different in flavor (although flows and colorings are certainly related notions). Here, the objects of interest are 3-flows with large support, and the backdrop is Tutte's famous 3-Flow Conjecture.