Hadwiger number

A graph G has a Hadwiger number no more than 2 if and only if it is a forest , and a three-vertex full minor can be formed by tightening the cycle in G.

A graph has a Hadwiger number of three or less if and only if its tree width does not exceed two, which is true if and only if any of its hinges is a parallel-serial graph .

The sum for the clicks of the two planar graphs and the Wagner graph gives a graph with the Hadwiger number equal to four.

From the Wagner theorem describing planar graphs by their forbidden subgraphs , it follows that the planar graphs have a Hadwiger number not exceeding 4. In some articles containing a proof of the theorem, Wagner ^[3] describes graphs with the Hadwiger number four or less precisely - these are graphs which can be formed with the help of sum-on-click operations of planar graphs with a Wagner graph having 8 vertices.

The graphs with the Hadwiger number of less than 5 include the top graphs and the embeddable graphs , both families have the full K ₆ graph among the forbidden minors ^[4]

Any graph with n vertices and a Hadwiger number k has O ( nk √ log k ) edges. This boundary is exact - for any k there exists a graph with Hadwiger number k having Ω ( nk √ log k ) edges ^{[5] [6] [7]} . If a graph G has a Hadwiger number k , then all its subgraphs also have a Hadwiger number not exceeding k , and this implies that the graph G must have degeneration O ( k √ log k ). Thus, graphs with a limited Hadwiger number are sparse graphs .

The Hadwiger hypothesis states that the Hadwiger number is always no less than the chromatic number of the graph G. That is, any graph with Hadwiger number k should have a coloring of maximum k colors. The case k = 4 is equivalent (according to Wagner’s characterization of graphs with this Hadwiger number) to the four -coloring problem on coloring planar graphs . The hypothesis was also proved for k ≤ 5, but remains unproved for large values ​​of k ^[8]

Due to the low density, graphs with a Hadwiger number not exceeding k can be colored using the greedy coloring algorithm in O ( k √ log k ) colors.

Checking whether the Hadwiger number of a given graph does not exceed a certain value of k is an NP-complete problem ^[9] , whence it follows that determining the Hadwiger number is an NP-hard problem . However, the problem is - there is an algorithm for determining the largest click minor in a time that depends only polynomially on the size of the graph, but exponentially on h ( G ) ^[10] . In addition, polynomial time algorithms can approximate the Hadwiger number substantially more accurately than the best polynomial time approximation (assuming that P ≠ NP) is the size of the largest full subgraphs ^[10] .

The achromatic number of a graph G is the size of the largest clique that can be formed by tightening a family of independent sets in G.

Uncountable click minors in infinite graphs can be characterized in terms of shelters that formalize avoidance strategies for some games — if the Hadwiger number is uncountable, it is equal to the order of greatest shelter in the graph ^[11] .

Any graph with Hadwiger number k has a maximum of n 2 ^{O ( k log log k )} clicks (full subgraphs) ^[12] .

Khalin ^[2] defined a class of graph parameters, which he called S -functions. Among them is the number of Hadwiger. These functions, which map graphs to integers, are required to take a zero value on , to be minor monotonous , an increase of one is required when adding a new vertex adjacent to all previous vertices, and from two values ​​for subgraphs along both to the sides of the click separator, the function should be more The set of such functions forms a complete lattice for the operations of taking the minimum or maximum elements. The bottom element in such a grid is the Hadwiger number, and the top element is the wood width .