- FindStat

Identifier

St001703: Graphs ⟶ ℤ

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