Combinatorics

Summary.

• Vizing's Theorem

• graphs are bipartite if and only if they contain no cycle of odd length

• Ramsey's Theorem

• graphs are bipartite if and only if they are \(2\)-colourable

• Brooks' Theorem

• Petersen graph

• Strong Perfect Graph Theorem

• Important definitions:

  • proper \(k\)-edge-colouring, \(k\)-edge-colourable

  • edge chromatic number, chromatic index

  • class one graph, class two graph

  • bipartite, bipartition

  • complete bipartite graph

  • proper \(k\)-colouring, \(k\)-colourable

  • chromatic number

  • \(k\)-critical

  • perfect graph

• Notation:

  • \(\displaystyle \chi'(G)\)

  • \(\displaystyle K_{m,n}\)

  • \(\displaystyle R(n_1, \ldots, n_c)\)

  • \(\displaystyle \chi(G)\)