Colourings.md (810B)
1 +++ 2 title = 'Colourings' 3 +++ 4 # Colourings 5 “colouring” is a way of labelling a graph 6 7 Edge colourings 8 9 - assign colours to edges such that edges incident on same vertex always have different colours 10 - a simple graph is k-edge colourable if E(G) can be partitioned into sets E1…Ek such that each pair of distinct edges in an E(1..k) isn’t incident to same vertex 11 - edge chromatic number Χ’(g) is minimal k for which G is edge-colourable 12 - Χ’(G) = Δ(G) or Δ(G) +1 13 - Δ(G) is maximum degree in graph 14 15 Vertex colourings 16 17 - simple graph..same as edge but with vertex 18 - Χ(G) chromatic number is minimal k for which G is k-vertex colourable 19 - Χ(G) ≤ Δ(G) + 1 20 - for any planar graph G, Χ(G) ≤ 4 21 - weaker bound: for any planar G, Χ(G) ≤ 5 22 - the proof for weaker bound can be asked