edit this statistic or download as text // json
Identifier
Values
=>
Cc0020;cc-rep
([],0)=>0 ([],1)=>0 ([],2)=>0 ([(0,1)],2)=>0 ([],3)=>0 ([(1,2)],3)=>2 ([(0,2),(1,2)],3)=>2 ([(0,1),(0,2),(1,2)],3)=>0 ([],4)=>0 ([(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)=>2 ([(0,3),(1,2),(1,3),(2,3)],4)=>2 ([(0,2),(0,3),(1,2),(1,3)],4)=>2 ([(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>4 ([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>0 ([],5)=>0 ([(3,4)],5)=>2 ([(2,4),(3,4)],5)=>2 ([(1,4),(2,4),(3,4)],5)=>4 ([(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)=>4 ([(2,3),(2,4),(3,4)],5)=>4 ([(0,4),(1,4),(2,3),(3,4)],5)=>4 ([(1,4),(2,3),(2,4),(3,4)],5)=>4 ([(0,4),(1,4),(2,3),(2,4),(3,4)],5)=>4 ([(1,3),(1,4),(2,3),(2,4)],5)=>2 ([(0,4),(1,2),(1,3),(2,4),(3,4)],5)=>4 ([(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>4 ([(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>4 ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>4 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5)=>4 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>4 ([(0,4),(1,3),(2,3),(2,4)],5)=>4 ([(0,1),(2,3),(2,4),(3,4)],5)=>2 ([(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)=>2 ([(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)=>2 ([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2 ([(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)=>3 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5)=>3 ([(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)=>0
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 villainy of a graph.
The villainy of a permutation of a proper coloring $c$ of a graph is the minimal Hamming distance between $c$ and a proper coloring.
The villainy of a graph is the maximal villainy of a permutation of a proper coloring.
References
[1] Jahanbekam, S., Lin, M.-R. Characterization of Graphs with Villainy 2 arXiv:2103.05816
Code
# extremely stupid code
def is_proper_coloring(G, c):
    """
    assume that G has vertices {0,...,n-1}.
    """
    return not any(c[v] in [c[u] for u in G[v]] for v in G)

def villainy_coloring(G, c):
    """
    assume that G has vertices {0,...,n-1}.
    """
    villainy = None
    for c_pi in Permutations(c):
        if is_proper_coloring(G, c_pi):
            d = sum(1 for c1, c2 in zip(c, c_pi) if c1 != c2)
            if villainy is None or d < villainy:
                villainy = d
                if villainy == 0:
                    return villainy
    return villainy

def statistic(G):
    G = G.relabel(inplace=False)
    n = G.num_verts()
    chi = G.chromatic_number()
    villainy = 0
    for c in sage.graphs.graph_coloring.all_graph_colorings(G, chi, vertex_color_dict=True):
        c = [c[i] for i in range(n)]
        for c_pi in Permutations(c):
            d = villainy_coloring(G, c_pi)
            villainy = max(villainy, d)
    return villainy

Created
Mar 11, 2021 at 13:16 by Martin Rubey
Updated
Mar 11, 2021 at 13:16 by Martin Rubey