---
author:
- 'David R. Wood'
title: Folding = Colouring
---

[^1]

The foldings of a graph[^2] are defined as follows. First, a graph $G$ is a *folding* of itself. Now suppose that $G$ is not complete. Let $G'$ be a graph obtained from $G$ by identifying two vertices at distance $2$ in $G$. Then every folding of $G'$ is a *folding* of $G$. The *folding number* of $G$, denoted by $f(G)$, is the minimum order of a complete folding of $G$. These concepts were introduced by @GGR-GC02, who determined the folding number of wheels and fans. Here we prove the following more general theorem, where $\chi(G)$ is the chromatic number of $G$.

For every graph $G$, $$f(G)=\chi(G).$$

First we prove that $\chi(G)\leq f(G)$. We proceed by induction on $|V(G)|$. In the base case, if $G$ is complete, then $f(G)=|V(G)|=\chi(G)$, and we are done. Otherwise, by the definition of folding-number, there is a graph $G'$ obtained from $G$ by identifying two vertices $v$ and $w$ at distance $2$ in $G$, such that $f(G')=f(G)$. By induction, $\chi(G')\leq f(G')$. If $v$ and $w$ are identified into a vertex $x$, then the colour assigned to $x$ in a colouring of $G'$ can be assigned to both $v$ and $w$ (since $v$ and $w$ are not adjacent, and every neighbour of $v$ or $w$ in $G$ is a neighbour of $x$ in $G'$). Thus $\chi(G)\leq\chi(G')\leq f(G')=f(G)$.

We now prove that $f(G)\leq\chi(G)$, again by induction on $|V(G)|$. In the base case, $G$ is complete and $f(G)=|V(G)|=\chi(G)$. Now assume $G$ is not complete.

We claim that $G$ has a $\chi(G)$-colouring such that some pair of vertices $v$ and $w$ at distance $2$ receive the same colour. First suppose that $G$ is an odd cycle. Then $\chi(G)=3$. Colour one vertex ‘red’, and colour the remaining vertices ‘blue’ and ‘green’ alternately around the cycle. This defines the claimed colouring. Now assume that $G$ is not an odd cycle. Take any $\Delta(G)$-colouring of $G$. We have $\chi(G)\leq\Delta(G)$ by Brooks’ Theorem [@Brooks41], where $\Delta(G)$ is the maximum degree of $G$. Let $u$ be a vertex of degree $\Delta(G)$. Two neighbours $v$ and $w$ of $u$ receive the same colour, as otherwise we have $\Delta(G)+1$ colours. Now $v$ and $w$ are not adjacent since they receive the same colour. Thus $v$ and $w$ are at distance $2$. This proves the claim.

Let $G'$ be the graph obtained from $G$ by identifying $v$ and $w$. Since the $\chi(G)$-colouring of $G$ defines a colouring of $G'$, it follows that $\chi(G')\leq\chi(G)$. By induction, $f(G')\leq\chi(G')$. Since $G'$ is a folding of $G$, it follows that $f(G)\leq f(G')$. Therefore $f(G)\leq f(G')\leq \chi(G')\leq \chi(G)$.

Folding is similar to edge-contraction (that is, identify two adjacent vertices, and delete the resulting loop). Perhaps this is relevant for Hadwiger’s Conjecture which, in light of Theorem 1, states that the minimum order of a complete folding of a graph $G$ is at most the maximum order of a complete contraction of $G$.

Theorem 1 suggests the following algorithm for colouring a graph $G$:\
*While $G$ is not complete, identify two vertices at distance $2$, and repeat.*\
First observe that this algorithm $2$-colours every bipartite graph. Theorem 1 implies that there exists a choice of vertices to identify at each step so that this algorithm optimally colours the given graph[^3]. Of course, choosing the right vertices is difficult[^4]. A natural heuristic is to choose a pair of vertices with the maximum number of common neighbours. Then the maximum possible number of parallel edges are created when the chosen vertices are identified. But this heuristic says nothing for graphs with girth at least $5$.

Note:  {#note .unnumbered}
------

Since this paper was first released, I have discovered that graph foldings were actually introduced by @CookEvans in 1979, who proved Theorem 1 with an identical proof to that presented here. Foldings have since been studied by a number of authors [@BS81; @Evans-JGT86; @GaoHahn-DM95; @BS-CN81].

[8]{} \[1\][\#1]{} \[1\][`#1`]{} urlstyle \[1\][doi:\#1]{}

<span style="font-variant:small-caps;">Norman Biggs</span>. Some heuristics for graph colouring. In <span style="font-variant:small-caps;">R. Nelson and R.J. Wilson</span>, eds., *Graph colourings*, pp. 87–96. Longman, 1990.

<span style="font-variant:small-caps;">R. L. Brooks</span>. On colouring the nodes of a network. *Proc. Cambridge Philos. Soc.*, 37:194–197, 1941.

<span style="font-variant:small-caps;">Fred Buckley and Lennox Superville</span>. The ajointed number and graph homomorphism problems. In *The theory and applications of graphs*, pp. 149–158. Wiley, New York, 1981.

<span style="font-variant:small-caps;">Fred Buckley and Lennox Superville</span>. Extremal results for the ajointed number. In *Proc. 12th Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I*, vol. 32 of *Congr. Numer.*, pp. 163–171. 1981.

<span style="font-variant:small-caps;">Curtis R. Cook and Anthony B. Evans</span>. Graph folding. In *Proc. 10th Southeastern Conference on Combinatorics, Graph Theory and Computing*, vol. XXIII–XXIV of *Congress. Numer.*, pp. 305–314. Utilitas Math., 1979.

<span style="font-variant:small-caps;">Anthony B. Evans</span>. Absolutely [$3$]{}-chromatic graphs. *J. Graph Theory*, 10(4):511–521, 1986.

<span style="font-variant:small-caps;">Guo-Gang Gao and Ge[ň]{}a Hahn</span>. Minimal graphs that fold onto [$K\sb n$]{}. *Discrete Math.*, 142(1-3):277–280, 1995.

<span style="font-variant:small-caps;">Severino V. Gervacio, Romulo C. Guerrero, and Helen M. Rara</span>. Folding wheels and fans. *Graphs Combin.*, 18(4):731–737, 2002.

[^1]: Departament de Matem[à]{}tica Aplicada II, Universitat Polit[è]{}cnica de Catalunya, Barcelona, Spain (`david.wood@upc.es`). Research supported by a Marie Curie Fellowship of the European Community under contract MEIF-CT-2006-023865, and by the projects MEC MTM2006-01267 and DURSI 2005SGR00692.

[^2]: All graphs considered are finite, undirected, loopless, connected, and possibly have parallel edges. A graph is *complete* if there is at least one edge between every pair of vertices.

[^3]: A similar property holds for the greedy sequential colouring algorithm: Every graph admits a linear ordering of its vertices, so that if the vertices are greedily coloured in this order, then an optimal colouring is obtained [@Biggs].

[^4]: Indeed, @GGR-GC02 showed that the complete graph on approximately $\sqrt{n/2}$ vertices is a folding of the wheel graph on $n$ vertices.
