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:
“At thirty years a woman asks her lover to give her back the esteem she has forfeited for his sake; she lives only for him, her thoughts are full of his future, he must have a great career, she bids him make it glorious; she can obey, entreat, command, humble herself, or rise in pride; times without number she brings comfort when a young girl can only make moan.”
—Honoré De Balzac (1799–1850)