Consider the following two ways to colour the vertices of a graph where the requirement that
adjacent vertices get distinct colours is relaxed. A colouring has" defect" $ d $ if each …

This is a survey of results on properties of random regular graphs, together with an
exposition of some of the main methods of obtaining these results. Related results on …

Over the past decade, many major advances have been made in the field of graph colouring
via the probabilistic method. This monograph provides an accessible and unified treatment …

This article surveys results on maximal k-degenerate graphs, k-trees, and related classes
including simple k-trees, k-paths, maximal outerplanar graphs, and Apollonian networks …

There is a great variety of colouring concepts and results in the literature. Here our focus is
to survey results on vertex colourings of graphs defined in terms of forbidden induced …

A graph is (k, d)‐colorable if one can color the vertices with k colors such that no vertex is
adjacent to more than d vertices of its same color. In this paper we investigate the existence …

In this chapter G=(V, E) denotes an arbitrary undirected graph without loops, where V={v 1, v
2,…, vn} is its vertex set and E={e 1, e 2,…, em}⊂(E× E) is its edge set. Two edges are …

Let G be a graph with maximum degree Δ (G). In this paper we prove that if the girth g (G) of
G is greater than 4 then its chromatic number, χ (G), satisfieswhere o (l) goes to zero as Δ (G) …

It is easy to see that if the maximum degree of G is 2, then the chromatic number/(G) is at
most 2+ 1. In fact there is a simple recursive greedy procedure for colouring a graph G with 2 …

Every graph with maximum degree Δ can be colored with (Δ+ 1) colors using a simple
greedy algorithm. Remarkably, recent work has shown that one can find such a coloring …