We study the evolution of the chromatic number of a random intersection graph and show
that, in a certain range of parameters, these random graphs can be colored optimally with …

A clique coloring of a graph is a coloring of the vertices so that no maximal clique is
monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring …

The clique chromatic number of a graph is the minimum number of colors in a vertex
coloring so that no maximal (with respect to containment) clique is monochromatic. We …

An intersection graph of n vertices assumes that each vertex is equipped with a subset of a
global label set. Two vertices share an edge when their label sets intersect. Random …

Abstract Algorithmic Graph Coloring and Random Graphs have long become one of the
most prominent branches of Combinatorics and Combinatorial Optimization. It is thus very …

An equitable colouring of a graph G is a vertex colouring where no two adjacent vertices are
coloured the same and, additionally, the colour class sizes differ by at most 1. The equitable …

The problem of coloring a graph with the minimum number of colors is well known to be NP-
hard, even restricted to k-colorable graphs for constant k≥ 3. On the other hand, it is known …

The chromatic number of a graph G is defined as the minimum number of colors required for
a vertex coloring where no two adjacent vertices are colored the same. The chromatic …

Informzpion Fg;:x!ing Coloring random graphs Page 1 Informzpion Fg;:x!ing ELSEVIER
Information Processing Letters 67 (1998) 7 1-74 Coloring random graphs Michael Krivelevich ‘ …

On the chromatic number of random graphs Page 1 On the Chromatic Number of Random Graphs
Colin McDiarmid Department of Statistics, University of Oxford, Oxford, England ABSTRACT …