论文标题
图形的多数边彩色
Majority Edge-Colorings of Graphs
论文作者
论文摘要
我们提出了大多数$ k $ - 颜色的图形$ g $的概念，这是$ g $的边缘颜色，带有$ k $颜色，因此，对于每个顶点$ u $ $ g $ $ g $，最多是$ g $的边缘，$ g $ cosist a $ u $的边缘具有相同的颜色。我们表明的最佳结果表明，每图至少$ 2 $的每图都有多数$ 4 $ - 边缘颜色，并且每张最低学位的每图至少$ 4 $都有大多数$ 3 $ - edge-the。此外，我们讨论了多数边颜色和一些相关开放问题的自然变化。
We propose the notion of a majority $k$-edge-coloring of a graph $G$, which is an edge-coloring of $G$ with $k$ colors such that, for every vertex $u$ of $G$, at most half the edges of $G$ incident with $u$ have the same color. We show the best possible results that every graph of minimum degree at least $2$ has a majority $4$-edge-coloring, and that every graph of minimum degree at least $4$ has a majority $3$-edge-coloring. Furthermore, we discuss a natural variation of majority edge-colorings and some related open problems.
