mirror of
https://github.com/TomHodson/tomhodson.github.com.git
synced 2025-06-26 10:01:18 +02:00
94 lines
4.0 KiB
HTML
94 lines
4.0 KiB
HTML
---
|
|
title: Lattice Colouring
|
|
excerpt:
|
|
layout: none
|
|
image:
|
|
|
|
---
|
|
<!DOCTYPE html>
|
|
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
|
|
<head>
|
|
<meta charset="utf-8" />
|
|
<meta name="generator" content="pandoc" />
|
|
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
|
|
<title>Lattice Colouring</title>
|
|
|
|
|
|
<script type="text/x-mathjax-config">
|
|
|
|
MathJax.Hub.Config({
|
|
"HTML-CSS": {
|
|
linebreaks: { automatic: true, width: "container" }
|
|
}
|
|
});
|
|
|
|
</script>
|
|
<script src="/assets/mathjax/tex-mml-svg.js" id="MathJax-script" async></script>
|
|
|
|
<script src="/assets/js/thesis_scrollspy.js"></script>
|
|
<script src="https://d3js.org/d3.v5.min.js" defer></script>
|
|
|
|
<link rel="stylesheet" href="/assets/css/thesis.css">
|
|
<script src="/assets/js/index.js"></script>
|
|
</head>
|
|
<body>
|
|
|
|
<!--Capture the table of contents from pandoc as a jekyll variable -->
|
|
{% capture tableOfContents %}
|
|
<br>
|
|
<nav aria-label="Table of Contents" class="page-table-of-contents">
|
|
<ul>
|
|
<li><a href="#lattice-colouring" id="toc-lattice-colouring">Lattice Colouring</a>
|
|
<ul>
|
|
<li><a href="#four-face-colourings-and-three-edge-colourings" id="toc-four-face-colourings-and-three-edge-colourings">Four-face-colourings and three-edge-colourings</a></li>
|
|
</ul></li>
|
|
</ul>
|
|
</nav>
|
|
{% endcapture %}
|
|
|
|
<!-- Give the table of contents to header as a variable so it can be put into the sidebar-->
|
|
{% include header.html extra=tableOfContents %}
|
|
|
|
<main>
|
|
|
|
<!-- Table of Contents -->
|
|
<!-- <nav id="TOC" role="doc-toc">
|
|
<ul>
|
|
<li><a href="#lattice-colouring" id="toc-lattice-colouring">Lattice Colouring</a>
|
|
<ul>
|
|
<li><a href="#four-face-colourings-and-three-edge-colourings" id="toc-four-face-colourings-and-three-edge-colourings">Four-face-colourings and three-edge-colourings</a></li>
|
|
</ul></li>
|
|
</ul>
|
|
</nav>
|
|
-->
|
|
|
|
<!-- Main Page Body -->
|
|
<div id="page-header">
|
|
<p>Appendices</p>
|
|
<hr />
|
|
</div>
|
|
<section id="lattice-colouring" class="level1">
|
|
<h1>Lattice Colouring</h1>
|
|
<section id="four-face-colourings-and-three-edge-colourings" class="level3">
|
|
<h3>Four-face-colourings and three-edge-colourings</h3>
|
|
<p>A four-face-colouring can be converted into a three-edge-colouring quite easily: 1. Assume the faces of G can be four-coloured with labels (0,1,2,3) 2. Label each edge of G according to <span class="math inline">\(i + j \;\textrm{mod}\; 3\)</span> where i and j are the labels of the face adjacent to that edge. For each edge label there are two face label pairs that do not share any face labels. i,e the edge label <span class="math inline">\(0\)</span> can come about either from faces <span class="math inline">\(0 + 3\)</span> or <span class="math inline">\(1 + 2\)</span>.</p>
|
|
<p>Explicitly, the mapping from face labels to edge labels is:</p>
|
|
<p><span class="math display">\[\begin{aligned}
|
|
0 + 3 \;\mathrm{or}\; 1 + 2 &= 0 \;\mathrm{mod}\; 3,\\
|
|
0 + 1 \;\mathrm{or}\; 2 + 3 &= 1 \;\mathrm{mod}\; 3,\\
|
|
0 + 2 \;\mathrm{or}\;1 + 3 &= 2 \;\mathrm{mod}\; 3.\\
|
|
\end{aligned}
|
|
\]</span></p>
|
|
<ol start="3" type="1">
|
|
<li><p>In a cubic planar G, a vertex v in G is always part of three faces and the colours of those faces determine the colours of the edges that connect to v. The three faces must take three distinct colours from the set <span class="math inline">\(\{0,1,2,3\}\)</span>.</p></li>
|
|
<li><p>From there, one can easily be convinced that those three distinct face colours can never produce repeated edge colours according to the <span class="math inline">\(i+j \;\mathrm{mod}\; 3\)</span> rule.</p></li>
|
|
</ol>
|
|
<p>This implies that all cubic planar graphs are three-edge-colourable. This does not apply to toroidal graphs. We have not yet generated a Voronoi lattices on the torus that is not three-edge-colourable. This suggests that Voronoi lattices may have additional structures that make them three-edge-colourable. Intuitively, it seems that the kinds of toroidal graphs that cannot be three-edge-coloured could never be generated by a Voronoi partition with more than a few seed points.</p>
|
|
</section>
|
|
</section>
|
|
|
|
|
|
</main>
|
|
</body>
|
|
</html>
|