Hajós construction

Applying the Hajós construction to two copies of K₄ by identifying a vertex from each copy into a single vertex (shown with both colors), deleting an edge incident to the combined vertex within each subgraph (dashed) and adding a new edge connecting the endpoints of the deleted edges (thick green), produces the Moser spindle.

Let G and H be two undirected graphs, vw be an edge of G, and xy be an edge of H. Then the Hajós construction forms a new graph that combines the two graphs by identifying vertices v and x into a single vertex, removing the two edges vw and xy, and adding a new edge wy.

For example, let G and H each be a complete graph K₄ on four vertices; because of the symmetry of these graphs, the choice of which edge to select from each of them is unimportant. In this case, the result of applying the Hajós construction is the Moser spindle, a seven-vertex unit distance graph that requires four colors.

As another example, if G and H are cycle graphs of length p and q respectively, then the result of applying the Hajós construction is itself a cycle graph, of length p + q − 1.

A graph G is said to be k-constructible (or Hajós-k-constructible) when it formed in one of the following three ways:[1]

• The complete graph K_k is k-constructible.
• Let G and H be any two k-constructible graphs. Then the graph formed by applying the Hajós construction to G and H is k-constructible.
• Let G be any k-constructible graph, and let u and v be any two non-adjacent vertices in G. Then the graph formed by combining u and v into a single vertex is also k-constructible. Equivalently, this graph may be formed by adding edge uv to the graph and then contracting it.

It is straightforward to verify that every k-constructible graph requires at least k colors in any proper graph coloring. Indeed, this is clear for the complete graph K_k, and the effect of identifying two nonadjacent vertices is to force them to have the same color as each other in any coloring, something that does not reduce the number of colors. In the Hajós construction itself, the new edge wy forces at least one of the two vertices w and y to have a different color than the combined vertex for v and x, so any proper coloring of the combined graph leads to a proper coloring of one of the two smaller graphs from which it was formed, which again causes it to require k colors.[1]

Hajós proved more strongly that a graph requires at least k colors, in any proper coloring, if and only if it contains a k-constructible graph as a subgraph. Equivalently, every k-critical graph (a graph that requires k colors but for which every proper subgraph requires fewer colors) is k-constructible.[2] Alternatively, every graph that requires k colors may be formed by combining the Hajós construction, the operation of identifying any two nonadjacent vertices, and the operations of adding a vertex or edge to the given graph, starting from the complete graph K_k.[3]

A similar construction may be used for list coloring in place of coloring.[4]

For k = 3, every k-critical graph (that is, every odd cycle) can be generated as a k-constructible graph such that all of the graphs formed in its construction are also k-critical. For k = 8, this is not true: a graph found by Catlin (1979) as a counterexample to Hajós's conjecture that k-chromatic graphs contain a subdivision of K_k, also serves as a counterexample to this problem. Subsequently, k-critical but not k-constructible graphs solely through k-critical graphs were found for all k ≥ 4. For k = 4, one such example is the graph obtained from the dodecahedron graph by adding a new edge between each pair of antipodal vertices[5]

Because merging two non-adjacent vertices reduces the number of vertices in the resulting graph, the number of operations needed to represent a given graph G using the operations defined by Hajós may exceed the number of vertices in G.[6]

More specifically, Mansfield & Welsh (1982) define the Hajós number h(G) of a k-chromatic graph G to be the minimum number of steps needed to construct G from K_k, where each step forms a new graph by combining two previously formed graphs, merging two nonadjacent vertices of a previously formed graph, or adding a vertex or edge to a previously formed graph. They showed that, for an n-vertex graph G with m edges, h(G) ≤ 2^{n2/3 − m + 1} − 1. If every graph has a polynomial Hajós number, this would imply that it is possible to prove non-colorability in nondeterministic polynomial time, and therefore imply that NP = co-NP, a conclusion considered unlikely by complexity theorists.[7] However, it is not known how to prove non-polynomial lower bounds on the Hajós number without making some complexity-theoretic assumption, and if such a bound could be proven it would also imply the existence of non-polynomial bounds on certain types of Frege system in mathematical logic.[7]

The minimum size of an expression tree describing a Hajós construction for a given graph G may be significantly larger than the Hajós number of G, because a shortest expression for G may re-use the same graphs multiple times, an economy not permitted in an expression tree. There exist 3-chromatic graphs for which the smallest such expression tree has exponential size.[8]

Koester (1991) used the Hajós construction to generate an infinite set of 4-critical polyhedral graphs, each having more than twice as many edges as vertices. Similarly, Liu & Zhang (2006) used the construction, starting with the Grötzsch graph, to generate many 4-critical triangle-free graphs, which they showed to be difficult to color using traditional backtracking algorithms.

In polyhedral combinatorics, Euler (2003) used the Hajós construction to generate facets of the stable set polytope.

• Catlin, P. A. (1979), "Hajós's graph-colouring conjecture: variations and counterexamples", Journal of Combinatorial Theory, Series B, 26 (2): 268–274, doi:10.1016/0095-8956(79)90062-5.
• Diestel, Reinhard (2006), Graph Theory, Graduate Texts in Mathematics, vol. 173 (3rd ed.), Springer-Verlag, pp. 117–118, ISBN 978-3-540-26183-4.
• Euler, Reinhardt (2003), "Hajós' construction and polytopes", Combinatorial optimization—Eureka, you shrink!, Lecture Notes in Computer Science, vol. 2570, Berlin: Springer-Verlag, pp. 39–47, doi:10.1007/3-540-36478-1_6, MR 2163949.
• Gravier, Sylvain (1996), "A Hajós-like theorem for list coloring", Discrete Mathematics, 152 (1–3): 299–302, doi:10.1016/0012-365X(95)00350-6, MR 1388650.
• Hajós, G. (1961), "Über eine Konstruktion nicht n-färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 116–117. As cited by Jensen & Toft (1994).
• Iwama, Kazuo; Pitassi, Toniann (1995), "Exponential lower bounds for the tree-like Hajós calculus", Information Processing Letters, 54 (5): 289–294, doi:10.1016/0020-0190(95)00035-B, MR 1336013.
• Jensen, Tommy R.; Royle, Gordon F. (1999), "Hajós constructions of critical graphs", Journal of Graph Theory, 30 (1): 37–50, doi:10.1002/(SICI)1097-0118(199901)30:1<37::AID-JGT5>3.0.CO;2-V, MR 1658542.
• Jensen, Tommy R.; Toft, Bjarne (1994), Graph Coloring Problems (2nd ed.), John Wiley and Sons, ISBN 978-0-471-02865-9.
• Koester, Gerhard (1991), "On 4-critical planar graphs with high edge density", Discrete Mathematics, 98 (2): 147–151, doi:10.1016/0012-365X(91)90039-5, MR 1144633.
• Kubale, Marek (2004), Graph Colorings, Contemporary Mathematics, vol. 352, American Mathematical Society, p. 156, ISBN 978-0-8218-3458-9.
• Liu, Sheng; Zhang, Jian (2006), "Using Hajós' construction to generate hard graph 3-colorability instances", Artificial Intelligence and Symbolic Computation, Lecture Notes in Computer Science, vol. 4120, Springer-Verlag, pp. 211–225, doi:10.1007/11856290_19.
• Mansfield, A. J.; Welsh, D. J. A. (1982), "Some colouring problems and their complexity", Graph theory (Cambridge, 1981), North-Holland Math. Stud., vol. 62, Amsterdam: North-Holland, pp. 159–170, MR 0671913.
• Pitassi, Toniann; Urquhart, Alasdair (1995), "The complexity of the Hajós calculus", SIAM Journal on Discrete Mathematics, 8 (3): 464–483, CiteSeerX 10.1.1.30.5879, doi:10.1137/S089548019224024X, MR 1341550.