论文标题
公平的树彩色间隔图的复杂性
Complexity of tree-coloring interval graphs equitably
论文作者
论文摘要
图形的公平树-$ k $ - 颜色是顶点$ k $颜色，使每个颜色类都诱发森林，任何两种颜色类别的大小最多都不同。 In this work, we show that every interval graph $G$ has an equitable tree-$k$-coloring for any integer $k\geq \lceil(Δ(G)+1)/2\rceil$, solving a conjecture of Wu, Zhang and Li (2013) for interval graphs, and furthermore, give a linear-time algorithm for determining whether a proper interval graph admits an equitable树-$ k $ - 给定整数$ k $的颜色。对于分开图的脱节，或$ k_ {1，r} $ - 带有$ r \ geq 4 $的免费间隔图，我们证明是$ w [1] $ - 很难确定是否存在按颜色数量或树木覆盖的颜色数量或颜色和最大程度的颜色数量和最大程度的颜色数量来参数化时是否有一个公平的树$ k $ - 颜色。
An equitable tree-$k$-coloring of a graph is a vertex $k$-coloring such that each color class induces a forest and the size of any two color classes differ by at most one. In this work, we show that every interval graph $G$ has an equitable tree-$k$-coloring for any integer $k\geq \lceil(Δ(G)+1)/2\rceil$, solving a conjecture of Wu, Zhang and Li (2013) for interval graphs, and furthermore, give a linear-time algorithm for determining whether a proper interval graph admits an equitable tree-$k$-coloring for a given integer $k$. For disjoint union of split graphs, or $K_{1,r}$-free interval graphs with $r\geq 4$, we prove that it is $W[1]$-hard to decide whether there is an equitable tree-$k$-coloring when parameterized by number of colors, or by treewidth, number of colors and maximum degree, respectively.
