Structure, Colouring, and Flows in Graphs

在离散数学中，图是点的集合，其中一些点可以用线连接。图是化学结构、电网、互联网、交通地图和许多其他对象的有用模型——任何可以被视为网络的东西都是抽象的图。涉及此类网络的现实世界问题受益于图论的定理、算法和洞察力。PI最感兴趣的是涉及结构、着色和相关概念的图问题，特别是将着色和结构联系起来的问题。这个项目特别关注四个子项目，包括浸入式、边缘着色和流动。前两个子项目都是由哈德维格猜想（Abu-Khzam- Langston猜想）的浸入式模拟所激发的，它将着色和浸入式联系起来。其中一个子项目试图在没有特定浸入的情况下找到图形的精确结构特征；另一种方法是更好地理解从旧图形创建新图形时，浸入式（和着色）是如何受到影响的。另一个引起PI极大兴趣的关于着色和结构的猜想是关于色指数的Goldberg-Seymour猜想。PI计划改进塔什基诺夫树的方法，这是用于逼近猜想结果的主要技术。最后一个子项目涉及流程，并且在风格上有些不同（尽管流程和着色当然是相关的概念）。在这里，感兴趣的对象是具有大支撑的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.