Structure, Colouring, and Flows in Graphs

图表中的结构、颜色和流程

• 批准号: 1600551
• 负责人: Jessica McDonald
• 金额: $ 12万
• 依托单位: Auburn University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1600551&HistoricalAwards=false
• 关键词: Structure; Colouring; Flows; 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.

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