---
tag: 0Y7VDAX8Q3
kind: definition
name: K-colourable graph
msc: [05C15]
defines: 0XHZW0VCPR
uses: [0874138YP6]
sources:
  - url: https://en.wikipedia.org/wiki/Graph_coloring
    locator: Vertex coloring
---

## Definition

Let $k$ be a natural number.
A [[graph|0JD5C82QMB]] $G$ is $k$-colourable if it has a [[colouring|0874138YP6]] with the set of colours $\{1, 2, \dots, k\}$.

## Remarks

A $k$-colourable graph is also $(k+1)$-colourable.
A graph is $2$-colourable if and only if it is [[bipartite|07DVHJ8N0A]].
The [[complete graph|03WKB2H474]] $K_n$ is $k$-colourable if and only if $k \ge n$.

## Explanations

### L1 human

A graph is $k$-colourable when $k$ colours are enough to colour it properly.
A triangle needs three colours, so it is $3$-colourable but not $2$-colourable.