论文标题
$ \！{} \ bmod k $彩色索引随机图
The $\!{}\bmod k$ chromatic index of random graphs
论文作者
论文摘要
图$ g $的$ \！{} \ bmod k $色度指数是$ g $的最小颜色数量，以每种颜色边缘所跨越的子图的跨度为$ 1 \！\！\！\！\ pmod k $。最近，作者证明了每个图的$ \！{} \ bmod k $色度索引最多是$ 198K-101 $，改善了Scott [离散数学的结果。 175，1-3（1997），289-291]。在这里，我们研究$ \！{} \ bmod k $彩色索引随机图。 We prove that for every integer $k\geq2$, there is $C_k>0$ such that if $p\geq C_kn^{-1}\log{n}$ and $n(1-p) \rightarrow\infty$ as $n\to\infty$, then the following holds: if $k$ is odd, then the $\!{}\bmod k$ chromatic index $ g（n，p）$的零售价几乎肯定等于$ k $，而如果$ k $甚至是$ k $，则$ \！{} \ bmod k $ k $ cholomation $ g（2n，p）$（分别为$ g（2n+1，p）$ nasty上几乎是$ k $ k $ k $ k $ $ k $ $ k $（分别是$ k $ k $ k+1 $ 1 $）。
The $\!{}\bmod k$ chromatic index of a graph $G$ is the minimum number of colors needed to color the edges of $G$ in a way that the subgraph spanned by the edges of each color has all degrees congruent to $1\!\!\pmod k$. Recently, the authors proved that the $\!{}\bmod k$ chromatic index of every graph is at most $198k-101$, improving, for large $k$, a result of Scott [Discrete Math. 175, 1-3 (1997), 289-291]. Here we study the $\!{}\bmod k$ chromatic index of random graphs. We prove that for every integer $k\geq2$, there is $C_k>0$ such that if $p\geq C_kn^{-1}\log{n}$ and $n(1-p) \rightarrow\infty$ as $n\to\infty$, then the following holds: if $k$ is odd, then the $\!{}\bmod k$ chromatic index of $G(n,p)$ is asymptotically almost surely equal to $k$, while if $k$ is even, then the $\!{}\bmod k$ chromatic index of $G(2n,p)$ (respectively $G(2n+1,p)$) is asymptotically almost surely equal to $k$ (respectively $k+1$).
