论文标题
可数图的多数可选性
Majority choosability of countable graphs
论文作者
论文摘要
在图的任何顶点着色中，一些边缘的颜色末端不同（\ emph {good}边），有些边缘是单色的（\ emph {bad}边缘）。在适当的着色中，所有边缘都很好。在\ emph {多数着色}中，对于每个顶点$ v $，事件的坏边数的数量不超过事件的好边缘数量到$ v $。 Lovász\ cite {lovasz}的众所周知的结果断言，每个有限图都有$ 2 $颜色的多数。对无限图的类似陈述是一个具有挑战性的开放问题，称为\ emph {不友好的分区猜想}。 我们考虑了多数着色的自然列表变体。图形为\ emph {多数$ k $ -Choosable}，如果从任意分配给顶点的任何大小$ k $的列表中都有多数颜色。我们证明，每个可计数的图表都是多数$ 4 $ - choosable。我们还考虑了针对有向图的多数颜色的自然类似物。我们证明，每个可数的挖掘者也是多数$ 4 $ - 可智能的。我们在不友好的分区猜想中提出列表和指示类似物，指出每个可数的图形都是多数$ 2 $ -CHOOSABLE，并且每个可计数的Digraph都是多数$ 3 $ -Choosable。
In any vertex coloring of a graph some edges have differently colored ends (\emph{good} edges) and some are monochromatic (\emph{bad} edges). In a proper coloring all edges are good. In a \emph{majority coloring} it is enough that for every vertex $v$, the number of bad edges incident to $v$ does not exceed the number of good edges incident to $v$. A well known result of Lovász \cite{Lovasz} asserts that every finite graph has a majority $2$-coloring. A similar statement for countably infinite graphs is a challenging open problem, known as the \emph{Unfriendly Partition Conjecture}. We consider a natural list variant of majority coloring. A graph is \emph{majority $k$-choosable} if it has a majority coloring from any lists of size $k$ assigned arbitrarily to the vertices. We prove that every countable graph is majority $4$-choosable. We also consider a natural analog of majority coloring for directed graphs. We prove that every countable digraph is also majority $4$-choosable. We pose list and directed analogs of the Unfriendly Partition Conjecture, stating that every countable graph is majority $2$-choosable and every countable digraph is majority $3$-choosable.
