Edge-colourings and Hamilton decompositions of graphs

图的边着色和汉密尔顿分解

• 批准号: EP/J008087/1
• 负责人: Deryk Osthus
• 金额: $ 24.52万
• 依托单位: University of Birmingham
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2012
• 资助国家: 英国
• 起止时间: 2012 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FJ008087%2F1
• 关键词: Edge; colourings; Hamilton; decompositions; graphs

A graph consists of a set of vertices, some of which are joined by edges. So every network like the internet gives rise to a graph. Moreover, many timetable scheduling problems can be modelled as graph colouring problems. Unfortunately, graph colouring problems are usually very hard in the sense that it is unlikely that there exists an efficient algorithm for solving them. So one tries to find natural conditions which guarantee the existence of good colourings. This has turned into an important area which has received much attention. However, many fundamental questions remain unsolved. The aim of the project is to solve several of these, based on a new notion of robustly decomposable graphs which we have developed recently. This method will also apply to long-standing problems on decompositions of graphs into Hamilton cycles. These problems in turn have applications to the famous Travelling Salesman Problem.

图由一组顶点组成，其中一些顶点由边连接。因此，像互联网这样的每个网络都会产生一张图表。此外，许多时间表调度问题都可以建模为图着色问题。不幸的是，图着色问题通常是非常困难的，因为不太可能存在有效的算法来解决它们。因此，人们试图找到保证良好色彩存在的自然条件。这已成为一个备受关注的重要领域。然而，许多根本性的问题仍然没有解决。该项目的目标是基于我们最近开发的稳健可分解图的新概念来解决其中的几个问题。该方法也将适用于图分解为哈密顿圈的长期问题。这些问题反过来又适用于著名的旅行商问题。

项目成果

Approximate Hamilton Decompositions of Robustly Expanding Regular Digraphs

鲁棒扩展正则图的近似哈密尔顿分解

• DOI: 10.1137/120880951
• 发表时间: 2013
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Osthus D

Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments

常规扩展器的汉密尔顿分解：大型锦标赛凯利猜想的证明

• DOI: 10.1016/j.aim.2013.01.005
• 发表时间: 2013
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: Kühn D

Edge-disjoint Hamilton cycles in graphs

• DOI: 10.1016/j.jctb.2011.10.005
• 发表时间: 2009-08
• 期刊: J. Comb. Theory B
• 作者: Demetres Christofides;D. Kühn;Deryk Osthus

Optimal Packings of Hamilton Cycles in Graphs of High Minimum Degree

高最小次数图中哈密顿循环的最优堆积

• DOI: 10.1017/s0963548312000569
• 发表时间: 2012
• 期刊: Combinatorics, Probability and Computing
• 作者: KÜHN D

Proof of the 1-factorization and Hamilton Decomposition Conjectures

• DOI: 10.1090/memo/1154
• 发表时间: 2014-01
• 期刊: International Journal of Cancer
• 影响因子: 6.4
• 作者: Béla Csaba;D. Kuhn;A. Lo;Deryk Osthus;Andrew Treglown