Overview of Graph Colouring and some Ramsey-type Numbers
Benjamin Fraser
Department of Computer Science and Mathematics, Nipissing University, 100 College Drive, P.O.Box 5002, North Bay, Ontario P1B 8L7, Canada.
Tzvetalin S. Vassilev *
Department of Computer Science and Mathematics, Nipissing University, 100 College Drive, P.O.Box 5002, North Bay, Ontario P1B 8L7, Canada.
*Author to whom correspondence should be addressed.
Abstract
We introduce the concept of graph colouring and discuss some classical results in this area. In particular, we consider the problem of finding the minimal graphs, complete or not, whose vertex or edge colouring contains or avoids certain subgraphs. This is generally known as Ramsey theory. We give short proofs of some elementary results in this area, and discuss their relationship to colouring integer sequences.
Keywords: Graph theory, graph colouring, critical graphs, extremal graphs, Ramsey numbers.