标题： 关于多数边着色的列表扩展 显示英文标题

标题： On list extensions of the majority edge colourings

摘要： 我们研究图的广义多数边着色的可能列表扩展，并提供了有关这些结果的几个结果。 给定一个图$G=(V,E)$，一个列表分配$L:E\to 2^C$以及某种多数容忍度$\alpha\in(0,1)$，$\alpha$-多数$L$-着色$G$是一种从给定列表中进行的着色$\omega:E\to C$，使得对于每个$v\in V$和每个$c\in C$，颜色为$c$的与$v$相关的边的数量不超过$\alpha\cdot d(v)$。 我们提出一个简单的论点，表明对于每个整数$k\geq 2$，每个最小度为$\delta\geq 2k^2-2k$的图，从大小为$k+1$的列表分配中，都允许进行$1/k$-多数$L$-着色。 这几乎达到了非列表设置中的最佳结果，并解决了关于基本多数边着色的一个猜想，即： 对于$k=2$，从列表中。 我们进一步讨论一些限制条件，这些条件允许在更一般的设置中获得相应结果，即 对于多样化的$\alpha=\alpha(c)$主导容差对于不同颜色$c\in C$。 Consider a list assignment $L:E\to 2^C$ with $\sum_{c\in L(e)}\alpha(c)\geq 1+\varepsilon$ for each edge $e$, and suppose that $\alpha(c)\geq a$ for every $c$ or $|L(e)|\leq\ell$ for all edges $e$, where $a\in(0,1)$, $\varepsilon>0$, $\ell\in\mathbb{N}$ are any given constants. 然后我们特别证明，如果满足$\delta(G)=\Omega(a^{-1}\varepsilon^{-2}\ln(a\varepsilon)^{-1})$或$\delta=\Omega(\ell^2\varepsilon^{-2})$，则从任何这样的列表分配中，存在一个$\alpha$优势的$L$色彩分配对$G$。我们还在每个边与一个具有固定优势容忍向量的颜色列表相关联的设定中加强了这些界限，这在一般的非列表情况下也适用。 显示英文摘要

摘要： We investigate possible list extensions of generalised majority edge colourings of graphs and provide several results concerning these. Given a graph $G=(V,E)$, a list assignment $L:E\to 2^C$ and some level of majority tolerance $\alpha\in(0,1)$, an $\alpha$-majority $L$-colouring of $G$ is a colouring $\omega:E\to C$ from the given lists such that for every $v\in V$ and each $c\in C$, the number of edges coloured $c$ which are incident with $v$ does not exceed $\alpha\cdot d(v)$. We present a simple argument implying that for every integer $k\geq 2$, each graph with minimum degree $\delta\geq 2k^2-2k$ admits a $1/k$-majority $L$-colouring from any assignment of lists of size $k+1$. This almost matches the best result in a non-list setting and solves a conjecture posed for the basic majority edge colourings, i.e. for $k=2$, from lists. We further discuss restrictions which permit obtaining corresponding results in a more general setting, i.e. for diversified $\alpha=\alpha(c)$ majority tolerances for distinct colours $c\in C$. Consider a list assignment $L:E\to 2^C$ with $\sum_{c\in L(e)}\alpha(c)\geq 1+\varepsilon$ for each edge $e$, and suppose that $\alpha(c)\geq a$ for every $c$ or $|L(e)|\leq\ell$ for all edges $e$, where $a\in(0,1)$, $\varepsilon>0$, $\ell\in\mathbb{N}$ are any given constants. Then we in particular show that there exists an $\alpha$-majority $L$-colouring of $G$ from any such list assignment, provided that $\delta(G)=\Omega(a^{-1}\varepsilon^{-2}\ln(a\varepsilon)^{-1})$ or $\delta=\Omega(\ell^2\varepsilon^{-2})$, respectively. We also strengthen these bounds within a setting where each edge is associated to a list of colours with a fixed vector of majority tolerances, applicable also in a general non-list case.