The Fractional Chromatic Number and the Hall Ratio
The Fractional Chromatic Number and the Hall Ratio
复制标题
分数色数和霍尔比
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Barnett
中科院分区：
文献类型：
--
作者：
J. Barnett
本文中的所有图都是有限简单图。α（G）是图G的点独立性。G的霍尔比定义为ρ（G）= max[ α（H）]| n（H）=| V（高）|和H <$G]，其中H <$G表示H是G的一个子图。图G的色数，记作χ（G），是标记G的顶点所需的最小颜色数，使得没有两个相邻的顶点接收相同的颜色。图G的b重染色是指给图G的每个顶点分配一个B颜色的集合，使得相邻的顶点接收不相交的颜色集合。然后我们说G是a：b-可着色的，如果它有一个b-重着色，其中B色来自a色的调色板。最小的a，其中G具有来自{1，...，a}是图G的b重色数，记为χB（G）.我们现在可以定义G的分数色数为χf（G）= infB χB B。已知对所有G，χ（G）≥ χf（G）≥ ρ（G）.已知在Kneser图类上，色数与Hall比之比是无界的。然而，如果K是一个Kneser图，则恰好χf（K）= ρ（K）。这就引出了一个问题：“χf ρ在所有有限简单图的域上有界吗？”在第二章中，我们定义了一个函数，它应该有助于识别给定图的霍尔比，我们讨论了所述函数的一般性质。在第三章中，我们通过考虑图W5的字典序幂和析取幂给出了回答上述问题的结果。在第四章中，我们通过考虑Mycielski图给出了回答上述问题的结果。
All graphs in this paper are both finite and simple. α(G) is the vertex independence of a graph, G. The Hall ratio of G is defined as ρ(G) = max[ α(H) | n(H) = |V (H)| and H ⊆ G] where H ⊆ G means that H is a subgraph of G. The chromatic number of G, denoted χ(G), is the smallest number of colors needed to label the vertices of G such that no two adjacent vertices receive the same color. A b-fold coloring of G is an assignment to each vertex of G a set of b colors so that adjacent vertices receive disjoint sets of colors. We then say that G is a:b-colorable if it has a b-fold coloring in which the b colors come from a palette of a colors. The least a for which G has a b-fold coloring from {1, ..., a} is the b-fold chromatic number of G and is denoted χb(G). We can now define the fractional chromatic number of G to be χf (G) = infb χb b . It is known that χ(G) ≥ χf (G) ≥ ρ(G) for all G. It is known that, on the class of Kneser graphs, the ratio of the chromatic number to the Hall ratio is unbounded. However, if K is a Kneser graph, then it happens that χf (K) = ρ(K). This begs the question, ”Is χf ρ bounded on the domain of all finite simple graphs?” In Chapter 2, we define a function that should help to identify the Hall ratio of a given graph and we discuss general properties of said function. In Chapter 3, we give results toward answering the question above by considering the lexicographic and disjunctive powers of the graph, W5. In Chapter 4, we give results toward answering the question above by considering the Mycielski graphs.