Δ(G)=11且不含有三角形,4-圈的平面图的完备染色

上官敏乐

（浙江树人大学 基础部，浙江 杭州 310015）

引言

图论起源于一个非常经典的问题——柯尼斯堡（Konigsberg）问题。

1738 年，瑞典数学家欧拉(Leornhard Euler)解决了柯尼斯堡问题。由此图论诞生。欧拉也成为图论的创始人。

1859 年，英国数学家汉密尔顿发明了一种游戏：用一个规则的实心十二面体，它的20 个顶点标出世界著名的20 个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即“绕行世界”。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个生成圈后来被称为汉密尔顿回路。这个问题后来就叫做汉密尔顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为汉密尔顿问题，从而引起广泛的注意和研究。

在图论的历史中，还有一个最著名的问题－－四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。这一问题最早于1852 年由Francis Guthrie 提出，最早的文字记载则现于德摩根于同一年写给哈密顿的信上。包括凯莱、肯普等在内的许多人都曾给出过错误的证明。泰特(Tait)、希伍德(Heawood)、拉姆齐和哈德维格(Hadwiger)对此问题的研究与推广引发了对嵌入具有不同亏格的曲面的图的着色问题的研究。一百多年后，四色问题仍未解决。1969 年，Heinrich Heesch 发表了一个用计算机解决此问题的方法。……