pith. sign in

arxiv: 0809.4726 · v2 · pith:MZT7U45Nnew · submitted 2008-09-26 · 🧮 math.CO · math.PR

The t-improper chromatic number of random graphs

classification 🧮 math.CO math.PR
keywords numberchromaticcolouringrandomt-improperasymptoticbehaviourchoices
0
0 comments X
read the original abstract

We consider the $t$-improper chromatic number of the Erd{\H o}s-R{\'e}nyi random graph $G(n,p)$. The t-improper chromatic number $\chi^t(G)$ of $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 $\chi^t(G(n,p))$ over the range of choices for the growth of $t = t(n)$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.