论文标题
关于恒星不交互联合的公平性可选性
On the Equitable Choosability of the Disjoint Union of Stars
论文作者
论文摘要
Equitable $k$-choosability is a list analogue of equitable $k$-coloring that was introduced by Kostochka, Pelsmajer, and West in 2003. It is known that if vertex disjoint graphs $G_1$ and $G_2$ are equitably $k$-choosable, the disjoint union of $G_1$ and $G_2$ may not be equitably $k$-choosable.给定任何$ m \ in \ mathbb {n} $ $ k_ {1，m} $的$ k $的值是公平的$ k $ - choosable。同样，尚不清楚平等的2 $可兑现图的完整表征。考虑到这些事实，我们研究了$ \ sum_ {i = 1}^n k_ {1，m_i} $的公平性可选性，$ n $ start的不相交联合。我们表明，确定$ \ sum_ {i = 1}^n k_ {1，m_i} $是公平的，当将两种颜色的两种颜色分配给每个顶点时，NP complete是np-complete。我们完全确定两颗星（或$ n \ geq 2 $相同恒星）的不相交联合是2个choos的，并且我们在任意$ k $的两颗恒星的不相交联合的公平$ k $可智力上呈现结果。
Equitable $k$-choosability is a list analogue of equitable $k$-coloring that was introduced by Kostochka, Pelsmajer, and West in 2003. It is known that if vertex disjoint graphs $G_1$ and $G_2$ are equitably $k$-choosable, the disjoint union of $G_1$ and $G_2$ may not be equitably $k$-choosable. Given any $m \in \mathbb{N}$ the values of $k$ for which $K_{1,m}$ is equitably $k$-choosable are known. Also, a complete characterization of equitably $2$-choosable graphs is not known. With these facts in mind, we study the equitable choosability of $\sum_{i=1}^n K_{1,m_i}$, the disjoint union of $n$ stars. We show that determining whether $\sum_{i=1}^n K_{1,m_i}$ is equitably choosable is NP-complete when the same list of two colors is assigned to every vertex. We completely determine when the disjoint union of two stars (or $n \geq 2$ identical stars) is equitably 2-choosable, and we present results on the equitable $k$-choosability of the disjoint union of two stars for arbitrary $k$.
