主題
Search

分數色數


f 為圖 G分數著色。則 f 的值之和稱為其權重,而分數著色的最小可能權重稱為分數色數 chi^*(G),有時也表示為 chi_f(G) (Pirnazar 和 Ullman 2002, Scheinerman 和 Ullman 2011) 或 chi_F(G) (Larson et al. 1995),有時也稱為集合色數 (Bollobás 和 Thomassen 1979)、終極色數 (Hell 和 Roberts 1982) 或多重著色數 (Hilton et al. 1973)。每個簡單圖都有一個分數色數,它是有理數或整數。

圖的分數色數可以使用線性規劃獲得,儘管計算是 NP-困難的。

任何樹和任何二分圖的分數色數都是 2 (Pirnazar 和 Ullman 2002)。

分數色數滿足

 omega(G)<=omega^*(G)=chi^*(G)<=chi(G),
(1)

其中 omega(G)團數omega^*(G)分數團數chi(G)色數 (Godsil 和 Royle 2001, pp. 141 和 145),其中結果 omega^*(G)=chi^*(G) 來自線性規劃的強對偶定理 (Larson et al. 1995; Godsil 和 Royle 2001, p. 141)。

圖的分數色數可能是一個小於色數的整數。例如,對於 Chvátal 圖chi^*=3chi=4。大於 1 的整數差也是可能的,例如,至少四個 28 個頂點的非 Cayley 頂點傳遞圖具有 chi-chi^*=2,並且許多 Kneser 圖具有更大的整數差。

FractionalColoringGimbelConjecture

Gimbel et al. (2019) 推測,每個 4 色 平面圖 的分數色數嚴格大於 3。反例由 18 節點的 Johnson 骨架圖 J_(92) 以及 Chiu et al. (2021) 給出的上述 18 節點示例提供。Chiu et al. (2021) 進一步證明,恰好有 17 個具有 色數 4 和分數色數 3 的 4-正則 18 頂點平面圖,並且沒有更小的圖具有這些值。

對於任何圖 G,

 chi^*(G)>=(|G|)/(alpha(G)),
(2)

其中 |G|頂點計數alpha(G)G獨立數。對於 頂點傳遞 G,等式始終成立,在這種情況下

 chi^*(G)=(|G|)/(alpha(G)),
(3)

(Scheinerman 和 Ullman 2011, p. 30)。但是,對於非頂點傳遞圖,等式也可能成立,包括 路徑圖 P_3爪形圖 K_(1,3)菱形圖等。

下表給出了特殊圖類的分數色數的閉合形式,其中 Mycielski 圖 M_n 由 Larsen et al. (1995) 討論,迴圈圖 C_(2n+1) 由 Scheinerman 和 Ullman (2011, p. 31) 討論,Kneser 圖 K(n,k) 由 Scheinerman 和 Ullman (2011, p. 32) 討論。

分數色數
迴圈圖 C_(2n+1)2+(1/n)
Kneser 圖 K(n,k),對於 k<n-1n/k
Mycielski 圖 M_na_2=2a_n=a_(n-1)+a_(n-1)^(-1)

下表給出了其他特殊情況。

反稜柱圖3, 4, 10/3, 3, 7/2, 16/5, 3, 10/3, 22/7, ...
啞鈴圖A0000273, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
雞尾酒會圖 K_(n×2)A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
完全圖 K_nA0000273, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...
迴圈圖 C_nA141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
空圖 K^__nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
頭盔圖4, 3, 7/2, 3, 10/3, 3, 13/4, 3, ...
Mycielski 圖 M_nA073833/A0738342, 5/2, 29/10, 941/290, 969581/272890, ...
平底鍋圖A141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
稜柱圖 Y_nA141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
太陽圖A0000273, 4, 5, 6, 7, 8, 9, 10, 11, ...
日卸圖 C_n circledot K_1A141310/A0579793, 2, 5/2, 2, 7/3, 2, 9/4, 2, 11/5, 2, 13/6, ...
網圖5/2, 2, 9/4, 2, 13/6, 2, 17/8, 2, 21/10, 2, 25/12, ...
輪圖 W_n4, 3, 7/2, 3, 10/3, 3, 13/4, 3, 16/5, 3, 19/6, 3, ...

另請參閱

色數分數團數分數著色分數邊色數

使用 探索

參考文獻

Bollobás, B. 和 Thomassen, A. "Set Colorourings of Graphs." Disc. Math. 25, 27-31, 1979.Chiu, M. K.; Felsner, S.; Scheucher, M.; Schröder, F.; Steiner, R.; 和 Vogtenhuber, B. "Coloring Circle Arrangements: New 4-Chromatic Planar Graphs." In Extended Abstracts EuroComb 2021 (Ed. J. Nešetril, G. Perarnau, J. Rué, 和 O. Serra). Cham, Switzerland: Birkhäuser, Cham., pp. 84-91, 2021.Gimbel, J.; Kündgen, A.; Li, B.; 和 Thomassen, C. "Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces." SIAM J. Disc. Math. 33, 1415-1430, 2019.Godsil, C. 和 Royle, G. "Fractional Chromatic Number." §7.3 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 137-138, 2001.Hell, P. 和 Roberts, F. "Analogues of the Shannon Capacity of a Graph." Ann. Disc. Math. 12, 155-162, 1982.Hilton, A. J. W.; Rado. R.; 和 Scott, S. H. "A (<5)-Colour Theorem for Planar Graphs." Bull. London Math. Soc. 5, 302-306, 1973.Larsen, M.; Propp, J.; 和 Ullman, D. "The Fractional Chromatic Number of Mycielski's Graphs." J. Graph Th. 19, 411-416, 1995.Lovász, L. "Semidefinite Programs and Combinatorial Optimization." In Recent Advances in Algorithms and Combinatorics (Ed. B. A. Reed 和 C. L. Sales). New York: Springer, pp .137-194, 2003,Pirnazar, A. 和 Ullman, D. H. "Girth and Fractional Chromatic Number of Planar Graphs." J. Graph Th. 39, 201-217, 2002.Scheinerman, E. R. 和 Ullman, D. H. Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, 2011.Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A057979, A073833, A073834, 和 A141310 in "The On-Line Encyclopedia of Integer Sequences."

在 上引用

分數色數

請引用為

Weisstein, Eric W. "分數色數。" 來自 Web 資源。 https://mathworld.tw/FractionalChromaticNumber.html

主題分類