主题
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, ...

另请参阅

色数分数团数分数着色分数边色数

使用 Wolfram|Alpha 探索

参考文献

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

在 Wolfram|Alpha 上引用

分数色数

请引用为

Weisstein, Eric W. "分数色数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/FractionalChromaticNumber.html

主题分类