Structure, Colouring, and Flows in Graphs

在离散数学中，图是一组点，其中一些可以通过线连接。图形是化学结构、电网、互联网、交通地图和许多其他对象的有用模型--任何可以被视为网络的东西，抽象地说，都是一个图形。涉及此类网络的真实的世界问题得益于图论的定理、算法和洞察力。PI最感兴趣的是涉及结构，着色和相关概念的图形问题-特别是连接着色和结构的问题。这个项目特别关注四个子项目，涉及沉浸，边着色和流动。前两个子项目都是由Hadwiger猜想（Abu-Khzam-兰斯顿猜想）的沉浸模拟激发的，它将着色和沉浸联系起来。一个子项目旨在找到没有特定浸入的图的精确结构特征;另一个子项目旨在更好地理解在从旧图创建新图时浸入（和着色）是如何受到影响的。第二个涉及着色和结构的猜想是关于色指数的Goldberg-Seymour猜想。PI计划致力于改进Tashkinov树的方法-用于猜想近似结果的主要技术。最后一个子项目涉及流，在风格上有些不同（尽管流和着色肯定是相关的概念）。在这里，感兴趣的对象是具有大支持的3-流，背景是Tutte著名的3-流猜想。

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.