论文标题
选择的公理在适当和区分着色中的作用
The role of the Axiom of Choice in proper and distinguishing colourings
论文作者
论文摘要
调用图形的着色，以区分保留其身份的唯一自动形态。我们研究了首选公理在顶点和边缘变体中某些适当或区分着色的作用，并特别强调了局部有限的连接图。我们表明，每个本地有限的连接图都具有与最多可数的颜色数量不同的颜色，或者只有在Kőnig的Lemma保持时，每个本地有限的连接图都具有适当的颜色。该语句适用于顶点和边缘着色。此外，我们表明，即使对于最高度3的每个连接图，也无法证明这种着色也存在。我们还制定了一些有关区分和适当着色的条件，这些条件与选择的公理相当。
Call a colouring of a graph distinguishing if the only automorphism which preserves it is the identity. We investigate the role of the Axiom of Choice in the existence of certain proper or distinguishing colourings in both vertex and edge variants with special emphasis on locally finite connected graphs. We show that every locally finite connected graph has a distinguishing colouring with at most countable number of colours or every locally finite connected graph has a proper colouring with at most countable number of colours if and only if Kőnig's Lemma holds. This statement holds for both vertex and edge colourings. Furthermore, we show that it is not provable in ZF that such colourings exist even for every connected graph with maximum degree 3. We also formulate a few conditions about distinguishing and proper colourings which are equivalent to the Axiom of Choice.
