graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a branch of mathematics, the Hajós construction is an operation on graphs named after that may be used to construct any critical graph or any graph whose

chromatic number In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...

is at least some given threshold.

The construction

Let and be two

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

s, be an edge of , and be an edge of . Then the Hajós construction forms a new graph that combines the two graphs by identifying vertices and into a single vertex, removing the two edges and , and adding a new edge . For example, let and each be a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...

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 In graph theory, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges. It can be dra ...

, a seven-vertex unit distance graph that requires four colors. As another example, if and are

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

s of length and respectively, then the result of applying the Hajós construction is itself a cycle graph, of length .

Constructible graphs

A graph is said to be -constructible (or Hajós--constructible) when it's formed in one of the following three ways:. *The complete graph is -constructible. *Let and be any two -constructible graphs. Then the graph formed by applying the Hajós construction to and is -constructible. *Let be any -constructible graph, and let and be any two non-adjacent vertices in . Then the graph formed by combining and into a single vertex is also -constructible. Equivalently, this graph may be formed by adding edge to the graph and then

contracting A contract is an agreement that specifies certain legally enforceable rights and obligations pertaining to two or more parties. A contract typically involves consent to transfer of goods, services, money, or promise to transfer any of those a ...

it.

Connection to coloring

It is straightforward to verify that every -constructible graph requires at least colors in any proper graph coloring. Indeed, this is clear for the complete graph , 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 forces at least one of the two vertices and to have a different color than the combined vertex for and , 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 colors. Hajós proved more strongly that a graph requires at least colors, in any proper coloring,

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...

it contains a -constructible graph as a subgraph. Equivalently, every - critical graph (a graph that requires colors but for which every proper subgraph requires fewer colors) is -constructible. Alternatively, every graph that requires 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 . A similar construction may be used for list coloring in place of coloring.

Constructibility of critical graphs

For , every -critical graph (that is, every odd cycle) can be generated as a -constructible graph such that all of the graphs formed in its construction are also -critical. For , this is not true: a graph found by as a

counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "student John Smith is not lazy" is a c ...

to Hajós's conjecture that -chromatic graphs contain a subdivision of , also serves as a counterexample to this problem. Subsequently, -critical but not -constructible graphs solely through -critical graphs were found for all . For , one such example is the graph obtained from the

dodecahedron In geometry, a dodecahedron (; ) or duodecahedron is any polyhedron with twelve flat faces. The most familiar dodecahedron is the regular dodecahedron with regular pentagons as faces, which is a Platonic solid. There are also three Kepler–Po ...

graph by adding a new edge between each pair of

antipodal Antipode or Antipodes may refer to: Mathematics * Antipodal point, the diametrically opposite point on a circle or ''n''-sphere, also known as an antipode * Antipode, the convolution inverse of the identity on a Hopf algebra Geography * Antipodes ...

vertices

The Hajós number

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 using the operations defined by Hajós may exceed the number of vertices in . More specifically, define the Hajós number of a -chromatic graph to be the minimum number of steps needed to construct from , 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 -vertex graph with edges, . If every graph has a polynomial Hajós number, this would imply that it is possible to prove non-colorability in

nondeterministic polynomial time In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs ve ...

, and therefore imply that NP =

co-NP In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and o ...

, a conclusion considered unlikely by complexity theorists.. 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 Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

. The minimum size of an expression tree describing a Hajós construction for a given graph may be significantly larger than the Hajós number of , because a shortest expression for 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..

Other applications

used the Hajós construction to generate an

infinite set In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Properties The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set ...

of 4-critical

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the Vertex (geometry), vertices and Edge (geometry), edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyh ...

s, each having more than twice as many edges as vertices. Similarly, used the construction, starting with the

Grötzsch graph In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example ...

, to generate many 4-critical triangle-free graphs, which they showed to be difficult to color using traditional

backtracking Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...

algorithms. In

polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral co ...

, used the Hajós construction to generate facets of the stable set

polytope In elementary geometry, a polytope is a geometric object with flat sides ('' faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an ...

Notes

References

*. *. *. *. *. As cited by . *. *. *. *. *. *. *. *. {{DEFAULTSORT:Hajos construction Graph operations Graph coloring