***************************************************************************** * www.FindStat.org - The Combinatorial Statistic Finder * * * * Copyright (C) 2019 The FindStatCrew * * * * 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