*****************************************************************************
*       www.FindStat.org - The Combinatorial Statistic Finder               *
*                                                                           *
*       Copyright (C) 2019 The FindStatCrew <info@findstat.org>             *
*                                                                           *
*    This information is distributed in the hope that it will be useful,    *
*    but WITHOUT ANY WARRANTY; without even the implied warranty of         *
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                   *
*****************************************************************************

-----------------------------------------------------------------------------
Statistic identifier: St001703

-----------------------------------------------------------------------------
Collection: Graphs

-----------------------------------------------------------------------------
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


-----------------------------------------------------------------------------
Statistic values:

([],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

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

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