Hajós construction
Encyclopedia
In graph theory
, 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 is at least some given threshold.
For example, let and each be a complete graph
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 and are cycle graph
s of length and respectively, then the result of applying the Hajós construction is itself a cycle graph, of length .
. 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 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.
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
, and therefore imply that NP = co-NP, 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
.
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.
s, each having more than twice as many edges as vertices. Similarly, used the construction, starting with the Grötzsch graph
, to generate many 4-critical triangle-free graph
s, which they showed to be difficult to color using traditional backtracking
algorithms.
In polyhedral combinatorics
, used the Hajós construction to generate facets
of the stable set
polytope
.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a branch of mathematics, the Hajós construction is an operation on graphs
Graph operations
Operations on graphs produce new graphs from old ones. They may be separated into the following major categories.-Elementary operations:These are sometimes called "editing operations" on graphs...
named after that may be used to construct any critical graph
Critical graph
In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a graph....
or any graph whose chromatic number is at least some given threshold.
The construction
Let and be two undirected graphs, let be an edge of , and let 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
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.-Properties:...
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
Moser spindle
In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges...
, a seven-vertex unit distance graph
Unit distance graph
In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one...
that requires four colors.
As another example, if and are cycle graph
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 connected in a closed chain. The cycle graph with n vertices is called Cn...
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 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 contractingEdge contractionIn graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it previously connected. Edge contraction is a fundamental operation in the theory of graph minors...
it.
Connection to coloring
It is straightforward to verify that every -constructible graph requires at least in any proper graph coloringGraph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
. 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
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
, if and only if it contains a -constructible graph as a subgraph. Equivalently, every -critical graph
Critical graph
In general the notion of criticality can refer to any measure.But in graph theory, when the term is used without any qualification, it almost always refers to the chromatic number of a 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 to Hajós's conjecture that -chromatic graphs contain a subdivision of , also serves as a counterexample to this problem. However, it remains unknown whether a construction of this type exists for every -critical graph with .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
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, and therefore imply that NP = co-NP, 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
Frege system
In proof complexity, a Frege system is a propositional proof system whose proofs are sequences of formulas derived using a finite set of sound and implicationally complete inference rules...
in mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
.
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 of 4-critical polyhedral graphPolyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
s, each having more than twice as many edges as vertices. Similarly, used the construction, starting with the Grötzsch graph
Grötzsch graph
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, and chromatic number 4. It is named after German mathematician Herbert Grötzsch, and its existence demonstrates that the assumption of planarity is necessary in Grötzsch's theorem ...
, to generate many 4-critical triangle-free graph
Triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
s, which they showed to be difficult to color using traditional backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
algorithms.
In polyhedral combinatorics
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....
, used the Hajós construction to generate facets
Facet (mathematics)
A facet of a simplicial complex is a maximal simplex.In the general theory of polyhedra and polytopes, two conflicting meanings are currently jostling for acceptability:...
of the stable set
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
polytope
Polytope
In elementary geometry, a polytope is a geometric object with flat sides, which exists in any general number of dimensions. A polygon is a polytope in two dimensions, a polyhedron in three dimensions, and so on in higher dimensions...
.