Title: Theory / Unimportant / CS / Fundamental / Graph / Bondy - Murty / 14 Colouring
Tags: algoToProblem complexity computer_to_instruction hasSeenConjDef

Name: A \(k\)-vertex colouring
Definition: A mapping \(c:V\to S\) with \(S\) a set of \(k\) colours
Page: 357
Chapter: 14
Section: 1
Variables: \(G\) a graph
\(k\in\mathbb N\)
Definition2: A \(k\)-partition of \(V\)
Name2: A \(k\) colouring

Name: A set of \(k\) colours
Definition: A set of cardinality \(k\), usually \(\{1,\dots,k\}\)
Page: 357
Chapter: 14
Section: 1
Variables: \(G\) a graph
\(k\in\mathbb N\)

Name: A propore colouring
Definition: A colouring (as a mapping) such that each adjacent vertices have a distinct colour
Page: 357
Chapter: 14
Section: 1
Variables: \(G\) a graph
\(k\in\mathbb N\)
Definition2: A colouring (as a \(k\)-partition) into stable sets

Name: A colour classe
Definition: A maximal set of vertices having the same colours
Page: 357
Chapter: 14
Section: 1
Variables: \(G\) a graph
\(c\) a colouring

Name: A \(k\)-colourable graph
Definition: A graph admitting a proper \(k\)-colouring
Page: 358
Chapter: 14
Section: 1
Variables: \(k\in\mathbb N\)

Question: The \(1\)-colourable graph are
Answer: exactly the empty graphs
Page: 358
Chapter: 14
Section: 1

Question: The \(2\)-colourable graph are
Answer: exactly the bipartite graphs
Page: 358
Chapter: 14
Section: 1

Name: The chromatic number of \(G\)
Definition: The least \(k\) such that \(G\) is \(k\)-colourable
Page: 358
Chapter: 14
Section: 1
Variables: \(G\) a graph,
Notation: \(\xi(G)\)
Example: \(3\) if odd, \(2\) if even
Example3: 2
Applied to: cycles
Example4: \(n\)
Applied to3: non empty forest
Applied to2: empty graph
Applied to4: \(K_n\)

Name: Hajós graph
Page: 358
Chapter: 14
Section: 1

Page: 359
Section: 1
Chapter: 14
Name: 3-coluring
Time complexity: NP-complete
Extra: Problem