- FindStat

edit this statistic or download as text // json

Identifier

St000822: Graphs ⟶ ℤ

Values

([],1) => 1

([],2) => 1

([(0,1)],2) => 2

([],3) => 1

([(1,2)],3) => 2

([(0,2),(1,2)],3) => 2

([(0,1),(0,2),(1,2)],3) => 3

([],4) => 1

([(2,3)],4) => 2

([(1,3),(2,3)],4) => 2

([(0,3),(1,3),(2,3)],4) => 2

([(0,3),(1,2)],4) => 2

([(0,3),(1,2),(2,3)],4) => 2

([(1,2),(1,3),(2,3)],4) => 3

([(0,3),(1,2),(1,3),(2,3)],4) => 3

([(0,2),(0,3),(1,2),(1,3)],4) => 3

([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 3

([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 4

([],5) => 1

([(3,4)],5) => 2

([(2,4),(3,4)],5) => 2

([(1,4),(2,4),(3,4)],5) => 2

([(0,4),(1,4),(2,4),(3,4)],5) => 2

([(1,4),(2,3)],5) => 2

([(1,4),(2,3),(3,4)],5) => 2

([(0,1),(2,4),(3,4)],5) => 2

([(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,4),(2,3),(3,4)],5) => 2

([(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(1,3),(1,4),(2,3),(2,4)],5) => 3

([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 3

([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 3

([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,3),(2,3),(2,4)],5) => 2

([(0,1),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 3

([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 3

([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 3

([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 3

([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4

([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4

([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 4

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 4

([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4

([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 5

([],6) => 1

([(4,5)],6) => 2

([(3,5),(4,5)],6) => 2

([(2,5),(3,5),(4,5)],6) => 2

([(1,5),(2,5),(3,5),(4,5)],6) => 2

([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 2

([(2,5),(3,4)],6) => 2

([(2,5),(3,4),(4,5)],6) => 2

([(1,2),(3,5),(4,5)],6) => 2

([(3,4),(3,5),(4,5)],6) => 3

([(1,5),(2,5),(3,4),(4,5)],6) => 2

([(0,1),(2,5),(3,5),(4,5)],6) => 2

([(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 2

([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,5),(2,4),(3,4)],6) => 2

([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 2

([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 2

([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 3

([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 3

([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(2,3)],6) => 2

([(1,5),(2,4),(3,4),(3,5)],6) => 2

([(0,1),(2,5),(3,4),(4,5)],6) => 2

([(1,2),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 2

([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 3

([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 3

([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3

([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3

([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 3

([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 3

([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 3

([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3

([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 3

>>> Load all 208 entries. <<<

search for individual values

searching the database for the individual values of this statistic

/ search for generating function

searching the database for statistics with the same generating function

click to show known generating functions

Description

The Hadwiger number of the graph.
Also known as clique contraction number, this is the size of the largest complete minor.

References

[1] wikipedia:Hadwiger number

Code

def statistic(G):
    min_bound = G.chromatic_number()
    if G.is_planar():
        max_bound = 4
    else:
        max_bound = G.num_verts()
    for k in range(min_bound, max_bound+1):
        try:
            G.minor(graphs.CompleteGraph(k))
        except ValueError:
            return k-1
    return max_bound

Created

May 23, 2017 at 22:08 by Martin Rubey

Updated

May 24, 2017 at 08:46 by Martin Rubey