The Hadwiger number h(G) of a graph G is the size k of the largest complete graph Kk that is a minor of G (or equivalently can be obtained by contracting edges of G). It is also known as the contraction clique number of G. The Hadwiger conjecture can be stated in the simple algebraic form χ(G) ≤ h(G) where χ(G) denotes the chromatic number of G. A related concept, the achromatic number of G, is the size of the largest clique that can be formed by contracting a family of independent sets in G).
Determining the Hadwiger number of a given graph is NP-complete but fixed-parameter tractable: there is an algorithm for finding the largest clique minor in an amount of time that depends only polynomially on the size of the graph, but exponentially in h(G). Additionally, polynomial time algorithms can approximate the Hadwiger number significantly more accurately than the best polynomial-time approximation (assuming P≠NP) to the size of the largest clique in a graph.
It is known that every graph G with h(G) = k has a vertex with at most O(k √log k) incident edges. By applying a greedy coloring algorithm that removes this low-degree vertex, colors the remaining graph, and then adds back the removed vertex and colors it, one can show that χ(G) = O(k √log k).
Read more about this topic: Hadwiger Conjecture (graph Theory)
Famous quotes containing the word number:
“Computers are good at swift, accurate computation and at storing great masses of information. The brain, on the other hand, is not as efficient a number cruncher and its memory is often highly fallible; a basic inexactness is built into its design. The brain’s strong point is its flexibility. It is unsurpassed at making shrewd guesses and at grasping the total meaning of information presented to it.”
—Jeremy Campbell (b. 1931)