主题
Search

1 类图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

维津定理 指出一个图可以使用 Delta 或 Delta+1 种颜色进行边着色，其中 Delta 是图的最大顶点度。一个边色数 等于 Delta 的图被称为 1 类图。

柯尼希线着色定理 指出所有二部图都是 1 类图。所有三次哈密顿图都是 1 类图，平面图且最大顶点度 Delta>7 的平面图也是 1 类图（Cole 和 Kowalik 2008）。

1 类图的边色数和分数边色数都等于 Delta。

看起来属于 1 类图的非二部图族（或至少其最小的成员都是 1 类图）包括国王图、Lindgren-Sousselier 和风车图（S. Wagon，私人通信，10 月 27-28 日，2011 年）。凯勒图是 1 类图（Jarnicki 等人 2015）。Aubert 和 Schneider (1982) 表明车图允许哈密顿分解，这意味着当它们具有偶数个顶点时是 1 类图，当它们具有奇数个顶点时是 2 类图（因为它们是奇正则的）。

Class1GraphsSimple

节点数为 n=1, 2, ... 的简单 1 类图的数量是 1, 2, 3, 10, 28, 145, ... (OEIS A099435)。

Class1GraphsSimpleConnected

类似地，简单连通 1 类图的数量是 1, 1, 1, 6, 17, 109, 821, 11050, 260150, ... (OEIS A099436; Royle)。

另请参阅

2 类图, 边色数, 柯尼希线着色定理, 维津定理

本条目的部分内容由 Ed Pegg, Jr. (作者链接) 贡献

本条目的部分内容由 Stan Wagon 贡献

使用 Wolfram|Alpha 探索

参考文献

Aubert, J. and Schneider, B. "循环的笛卡尔和与两个哈密顿循环的并集的分解为哈密顿循环。" Disc. Math. 38, 7-16, 1982.Cole, R. and Kowalik, L. "用于平面图边着色的新线性时间算法。" Algorithmica 50, 351-368, 2008.Jarnicki, W.; Myrvold, W.; Saltzman, P.; and Wagon, S. "凯勒图、Mycielski 图和皇后图的已证明和猜想的性质。" To appear in Ars Math. Comtemp. 2017.Royle, G. "2 类图。" http://school.maths.uwa.edu.au/~gordon/remote/graphs/#class2.Sloane, N. J. A. 序列 A099435 和 A099436 在 "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 上引用

1 类图

请引用为

Pegg, Ed Jr.; Wagon, Stan; 和 Weisstein, Eric W. "1 类图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Class1Graph.html

主题分类