Identifier
Identifier
Values
([],1) generating graphics... => 0
([],2) generating graphics... => 1
([(0,1)],2) generating graphics... => 1
([],3) generating graphics... => 1
([(0,2),(1,2)],3) generating graphics... => 2
([(0,1),(0,2),(1,2)],3) generating graphics... => 2
([],4) generating graphics... => 1
([(1,3),(2,3)],4) generating graphics... => 1
([(1,2),(1,3),(2,3)],4) generating graphics... => 2
([(0,3),(1,3),(2,3)],4) generating graphics... => 2
([(0,3),(1,2),(2,3)],4) generating graphics... => 1
([(0,3),(1,2),(1,3),(2,3)],4) generating graphics... => 2
([(0,2),(0,3),(1,2),(1,3),(2,3)],4) generating graphics... => 2
([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) generating graphics... => 3
([],5) generating graphics... => 1
([(2,4),(3,4)],5) generating graphics... => 1
([(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,4),(1,4),(2,4),(3,4)],5) generating graphics... => 2
([(1,4),(2,3),(3,4)],5) generating graphics... => 1
([(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 3
([(0,1),(2,4),(3,4)],5) generating graphics... => 1
([(0,4),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,4),(1,3),(2,3),(2,4)],5) generating graphics... => 1
([(0,4),(1,3),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 3
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 3
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 3
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 4
([(0,1),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,3),(1,2),(1,4),(2,4),(3,4)],5) generating graphics... => 2
([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) generating graphics... => 2
([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) generating graphics... => 3
([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) generating graphics... => 2
([],6) generating graphics... => 1
([(3,5),(4,5)],6) generating graphics... => 1
([(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,5),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(2,5),(3,4),(4,5)],6) generating graphics... => 1
([(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(1,2),(3,5),(4,5)],6) generating graphics... => 1
([(1,5),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(1,5),(2,4),(3,4),(3,5)],6) generating graphics... => 1
([(1,5),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 4
([(1,2),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(1,4),(2,3),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,5),(2,4),(3,4)],6) generating graphics... => 1
([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,5),(2,3),(2,4),(3,4)],6) generating graphics... => 2
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) generating graphics... => 2
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) generating graphics... => 2
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) generating graphics... => 2
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) generating graphics... => 2
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,1),(2,5),(3,4),(4,5)],6) generating graphics... => 1
([(0,1),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 4
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,4),(2,3),(2,4),(3,5)],6) generating graphics... => 1
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) generating graphics... => 2
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 4
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) generating graphics... => 2
([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) generating graphics... => 2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 4
([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 5
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 3
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 4
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) generating graphics... => 4
Description
The Colin de Verdière graph invariant.
References
[1] wikipedia:Colin_de_Verdière_graph_invariant
[2] van der Holst, H., Lovász, L., Schrijver, A. The Colin de Verdière graph parameter MathSciNet:1673503
[3] Goldberg, F., Berman, A. On the Colin de Verdière number of graphs MathSciNet:2775745
[4] Tait, M. The Colin de Verdi\`ere parameter, excluded minors, and the spectral radius arXiv:1703.09732
Code
def statistic(G):
    mu = lower_and_upper_bounds(G.copy(immutable=True))
    if mu[0] == mu[1]:
        return mu[0]

@cached_function
def lower_and_upper_bounds(G, assume_Colin_conjecture=False):
    if G.is_clique():
        return (G.num_verts()-1, G.num_verts()-1)
    
    if G.num_verts() >= 2 and G.num_edges() == 0:
        # Goldberg, Berman (2011), prop. 6.7
        return (1,1)

    w = G.clique_number()
    # Goldberg, Berman (2011), cor. 2.4
    lower = w-1
    # Goldberg, Berman (2011), thm. 2.3 and mu(K_n)=n-1
    upper = G.num_verts()-1

    degrees = G.degree()
    if max(degrees) == 2 and G.is_forest():
        # Goldberg, Berman (2011), thm 2.6 (1)
        upper = 1
    elif G.is_circular_planar():
        # Goldberg, Berman (2011), thm 2.6 (2)
        upper = 2
    elif G.is_planar():
        # Goldberg, Berman (2011), thm 2.6 (3)
        upper = 3

    # Goldberg, Berman (2011), thm 5.4
    upper = min(upper, G.treewidth()+1)

    if G.is_chordal():
        # Goldberg, Berman (2011), thm 4.1
        upper = min(upper, w)

    if assume_Colin_conjecture:
        # Goldberg, Berman (2011), conj 2.7
        lower = max(lower, G.chromatic_number()-1)

    # Holst, Lovasz, and Schrijver (1999)
    # see Tait (2017), thm 7
    for v, d in G.degree(labels=True).iteritems():
        H = G.copy(immutable=False)
        H.delete_vertex(v)
        H = H.copy(immutable=True)
        mu_H = lower_and_upper_bounds(H, assume_Colin_conjecture=assume_Colin_conjecture)
        # equality is achieved if G has at least one edge (which we know at this point) and
        # v is connected to all other vertices
        if mu_H[0] == mu_H[1] and d == G.num_verts()-1:
            return (mu_H[0]+1, mu_H[0]+1)
                    
        upper = min(upper, mu_H[1] + 1)
        if lower == upper:
            return (lower, upper)

    return (lower, upper)

Created
Mar 30, 2017 at 09:11 by Martin Rubey
Updated
Mar 31, 2017 at 11:31 by Martin Rubey