Complete minors in graphs with only a few colourings

仅用少量着色即可完成图表中的未成年人

• 批准号: 327533333
• 负责人: Professor Dr. Matthias Kriesell
• 金额: --
• 依托单位: Arbeitsgruppe Diskrete Mathematik und Algebra
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/327533333?language=en
• 关键词: Complete; minors; graphs; only; few

Hadwigers Conjecture from 1943 states that for every natural number k every graph either admits a colouring of the vertices with k colours such that adjacent vertices receive distinct colours, or contains k+1 many disjoint, connected, pairwise adjacent subgraphs (a so-called complete minor of order k+1). The problem is one of the most important open questions in graph theory. We consider the case that the graph under consideration admits only a restricted number of colourings with k colours.

1943年的Hadwigers猜想指出，对于每个自然数k，每个图要么允许顶点用k种颜色着色，使得相邻的顶点接收不同的颜色，要么包含k+1个不相交的，连通的，成对相邻的子图（所谓的k+1阶完全子图）。该问题是图论中最重要的开放问题之一。我们考虑的情况下，所考虑的图只允许有限数量的着色与k颜色。

项目成果

Long cycles and spanning subgraphs of locally maximal 1‐planar graphs

局部最大 1â平面图的长循环和跨越子图

• DOI: 10.1002/jgt.22542
• 发表时间: 2020
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Igor Fabrici;Jochen Harant;Tomáš Madaras;Samuel Mohr;Roman Soták;Carol T. Zamfirescu
• 通讯作者: Carol T. Zamfirescu

Rooted Complete Minors in Line Graphs with a Kempe Coloring

用 Kempe 着色线形图根植完整未成年人

• DOI: 10.1007/s00373-019-02012-7
• 发表时间: 2019
• 期刊: Graphs and Combinatorics
• 影响因子: 0.7
• 作者: Matthias Kriesell;Samuel Mohr
• 通讯作者: Samuel Mohr

A construction of uniquely colourable graphs with equal colour class sizes

具有相同颜色类别大小的独特彩色图表的构造

• DOI: 10.1016/j.dam.2020.11.015
• 发表时间: 2021
• 期刊: Discret. Appl. Math.
• 作者: Samuel Mohr