Colourings.html (1952B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-0.7313327193260193"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 10:07:01 +0000"/><meta name="latitude" content="52.3345077115161"/><meta name="longitude" content="4.866741210123743"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:46:40 +0000"/><title>Colourings</title></head><body><div>“colouring” is a way of labelling a graph</div><div><br/></div><div>Edge colourings</div><ul><li><div>assign colours to edges such that edges incident on same vertex always have different colours</div></li><li><div>a simple graph is k-edge colourable if E(G) can be partitioned into sets E<span style="vertical-align: sub;">1</span>…E<span style="vertical-align: sub;">k</span> such that each pair of distinct edges in an E(1..k) isn’t incident to same vertex</div></li><li><div>edge chromatic number Χ’(g) is minimal k for which G is edge-colourable</div></li><li><div>Χ’(G) = Δ(G) or Δ(G) +1</div></li><ul><li><div>Δ(G) is maximum degree in graph</div></li></ul></ul><div><br/></div><div>Vertex colourings</div><ul><li><div>simple graph..same as edge but with vertex</div></li><li><div>Χ(G) chromatic number is minimal k for which G is k-vertex colourable</div></li><li><div>Χ(G) ≤ Δ(G) + 1</div></li><li><div>for any planar graph G, Χ(G) ≤ 4</div></li><ul><li><div>weaker bound: for any planar G, Χ(G) ≤ 5</div></li><li><div>the proof for weaker bound can be asked</div></li></ul></ul><div><br/></div></body></html>