The t-Improper Chromatic Number of Random Graphs
The t-Improper Chromatic Number of Random Graphs
复制标题
随机图的t-不当色数
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
C. McDiarmid
中科院分区：
文献类型：
--
作者：
Ross J. Kang;C. McDiarmid
我们考虑Erdős-Rényi随机图Gn，p的t-非正常色数。t-不正当着色数χt(G)是顶点着色所需的最小颜色数，其中每个颜色类在最多t处诱导出最大程度的子图。如果t = 0，则这是通常的适当着色概念。当边缘概率p为常数时，我们详细描述了χt（Gn,p）在t = t(n)增长的选择范围内的渐近行为。
We consider the t-improper chromatic number of the Erdős–Rényi random graph Gn,p. The t-improper chromatic number χt(G) is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most t. If t = 0, then this is the usual notion of proper colouring. When the edge probability p is constant, we provide a detailed description of the asymptotic behaviour of χt(Gn,p) over the range of choices for the growth of t = t(n).