论文标题
带有小调色板的图表的表征
A characterization of graphs with small palette index
论文作者
论文摘要
给定图$ g $的边缘颜色，我们将每个顶点$ v $ $ g $都关联到$ v $的边缘事件上出现的一组颜色。 $ g $的调色板指数定义为这种不同集合的最小数量，占所有可能的边缘$ g $。带有小调色板索引的图形构造的边缘色几乎可以被认为是对称的，因为其顶点周围几乎没有不同的颜色集。带有调色板索引$ 1 $的图形是$ r $ regular Graphs承认$ r $ - 边缘颜色，而带有调色板索引$ 2 $的常规图形不存在。在这里，我们表征了所有带有调色板索引的图表，即$ 2 $或$ 3 $，在常规子图中存在合适的分解。作为推论，我们获得了带有调色板索引$ 3 $的常规图表的完整表征。
Given an edge-coloring of a graph $G$, we associate to every vertex $v$ of $G$ the set of colors appearing on the edges incident with $v$. The palette index of $G$ is defined as the minimum number of such distinct sets, taken over all possible edge-colorings of $G$. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index $1$ are $r$-regular graphs admitting an $r$-edge-coloring, while regular graphs with palette index $2$ do not exist. Here, we characterize all graphs with palette index either $2$ or $3$ in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index $3$.
