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:
“A child’s self-image is more like a scrapbook than a single snapshot. As the child matures, the number and variety of images in that scrapbook may be far more important than any individual picture pasted inside it.”
—Lawrence Kutner (20th century)