Graph colouring

Question 1

What is colouring of a graph, G?

Answer 1

An assignment of one colour to each vertex such that adjacent vertices receive different colours. Formally a function f:V(G)-> C such that f(v) does not equal f(w) for every vw in E(G) where C is a set of colours.

Question 2

What is a k-colouring?

Answer 2

A colouring where |C| is at most k. If G is k-colourable it is k+n-colourable

Question 3

What is the chromatic number \chi(G)?

Answer 3

The minimum integer k such that there is a k-colouring in G.

Question 4

\chi(G) \leq k iff G is ___-___
\chi(G) \geq k iff G is ___ ___-___

Answer 4

\chi(G) \leq k iff G is k-colourable
\chi(G) \geq k iff G is not (k-1)-colourable

Question 5

What is K_{n_1,n_2,…,n_k}?

Answer 5

The multipartite graph on k partitions or the k-partite graph. Which is k-colourable.

Question 6

What is a colour class?

Answer 6

A set independent vertices coloured the same colour.

Question 7

A graph is k-colourable iff its vertex set can be ___ ___ ___ ___ ___

Answer 7

A graph is k-colourable iff its vertex set can be partitioned into k independent sets

Question 8

What is the minimum size of the largest colour class in a k-colouring?

Answer 8

|V(G)|/k

Question 9

In a k-colouring what is the max independent set alpha(G) un upper bound of?

Answer 9

|V(G)/chi(G)

Question 10

alpha(G) \geq ___

Answer 10

|V(G)|/chi(G)

Question 11

When is a graph, G, k-degenerate? And what is the degeneracy of G?

Answer 11

A graph is k-degenerate if every subgraph has a vertex of at most degree k. The degeneracy is the maximum taken over all the minimum degrees, delta(G), of all the subgraphs of G. Or it is the minimum k such that G is k-degenerate.

Question 12

Every k-degenerate graph is ___ ___

Answer 12

(k+1)-colourable

Question 13

Every graph with maximum degree ___ is ___-___ and therefore ___-___

Answer 13

Every graph with maximum degree Delta is Delta-degenerate and therefore Delta+1-colourable

Question 14

For every integer k \geq 1 there is a triangle-free k-degenerate graph G with ___=___

Answer 14

chi(G)=k+1

Question 15

What is the girth of graph G?

Answer 15

The length of the shortest cycle in G, if it contains a cycle.

Question 16

Erdos’ Theorem for girth: For all integers k and g there is a graph G with girth ___ ___ ___ and chromatic number ___ ___ ___

Answer 16

For all integers k and g there is a graph G with girth greater than g and chromatic number greater than k.

Question 17

For every integer k \geq 2 there is a graph G_k with girth ___ ___ ___ that is ___ ___-___

Answer 17

For every integer k \geq 2 there is a graph G_k with girth at least 6 that is not k-colourable.

Question 18

State Brook’s Theorem

Answer 18

Every graph G with maximum degree Delta is Delta-colourable unless some component of G is K_{Delta+1} or Delta=2 and some component of G is an odd cycle.

Question 19

What is a k-clique in a graph G?

Answer 19

A set of k pairwise adjacent vertices in G.