主題
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 貢獻

使用 探索

參考文獻

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."

在 上引用

1 類圖

請引用為

Pegg, Ed Jr.; Wagon, Stan; 和 Weisstein, Eric W. "1 類圖。" 來自 Web 資源。 https://mathworld.tw/Class1Graph.html

主題分類