论文标题
Grundy着色和朋友，半雕像，双插曲
Grundy Coloring & friends, Half-Graphs, Bicliques
论文作者
论文摘要
第一个合适的着色是一种启发式，它分配给每个顶点，以指定顺序$σ$到达，最小的可用颜色。 Grundy着色的问题询问，最对抗性顶点订购$σ$，即首先要在所有可能的顶点订购中需要的最大颜色数量需要多少颜色。自1939年Grundy成立以来，Grundy着色的结构和算法方面已被检查。蛮力$ f（k）n^{2^{k-1}} $ - 在一般图上涂上Grundy着色的时间算法并不难获得，其中$ k $是最对抗性顶点订购所需的颜色数量。有人询问多次对$ n $的指数中$ k $的依赖是可以避免或减少的，并且到目前为止，它的答案似乎难以捉摸。我们证明，Grundy的着色是W [1] - hard，而蛮力算法在指数时间假设下实质上是最佳的，因此通过负面解决了这个问题。 我们的w [1] - hardness证明中的关键成分是使用所谓的半盖作为构建块将颜色从一个顶点传输到另一个顶点。利用半雕刻，我们还证明了b-Chromatic核心是w [1] - hard，其参数化的复杂性是由Panolan等人提出的。 [JCSS '17]。一个自然的后续问题是，参数化的复杂性如何在没有（大）半图的情况下变化。我们在$ k_ {t，t，t} $上建立固定参数的障碍 - b-chrostic核心和部分grundy着色的免费图形，迈出了回答这个问题的一步。关键的障碍结果基础的关键组合引理可能具有独立的关注。
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order $σ$, the smallest available color. The problem Grundy Coloring asks how many colors are needed for the most adversarial vertex ordering $σ$, i.e., the maximum number of colors that the first-fit coloring requires over all possible vertex orderings. Since its inception by Grundy in 1939, Grundy Coloring has been examined for its structural and algorithmic aspects. A brute-force $f(k)n^{2^{k-1}}$-time algorithm for Grundy Coloring on general graphs is not difficult to obtain, where $k$ is the number of colors required by the most adversarial vertex ordering. It was asked several times whether the dependency on $k$ in the exponent of $n$ can be avoided or reduced, and its answer seemed elusive until now. We prove that Grundy Coloring is W[1]-hard and the brute-force algorithm is essentially optimal under the Exponential Time Hypothesis, thus settling this question by the negative. The key ingredient in our W[1]-hardness proof is to use so-called half-graphs as a building block to transmit a color from one vertex to another. Leveraging the half-graphs, we also prove that b-Chromatic Core is W[1]-hard, whose parameterized complexity was posed as an open question by Panolan et al. [JCSS '17]. A natural follow-up question is, how the parameterized complexity changes in the absence of (large) half-graphs. We establish fixed-parameter tractability on $K_{t,t}$-free graphs for b-Chromatic Core and Partial Grundy Coloring, making a step toward answering this question. The key combinatorial lemma underlying the tractability result might be of independent interest.
