***************************************************************************** * 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: St001117 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- Description: The game chromatic index of a graph. Two players, Alice and Bob, take turns colouring properly any uncolored edge of the graph. Alice begins. If it is not possible for either player to colour a edge, then Bob wins. If the graph is completely colored, Alice wins. The game chromatic index is the smallest number of colours such that Alice has a winning strategy. ----------------------------------------------------------------------------- References: [1] [[wikipedia:Graph coloring game]] [2] Andres, S. D., Hochstättler, W., Schallück, C. The game chromatic index of wheels [[MathSciNet:2825608]] ----------------------------------------------------------------------------- Code: def statistic(G, verbose=False): """Return the smallest number such that Alice has a winning strategy. EXAMPLES: sage: [statistic(graphs.PathGraph(r)) for r in range(2,8)] [1, 2, 2, 3, 3, 3] sage: [statistic(graphs.CycleGraph(r)) for r in range(2,8)] [1, 3, 3, 3, 3, 3] sage: [statistic(graphs.StarGraph(r)) for r in range(2,8)] [2, 3, 4, 5, 6, 7] sage: [statistic(graphs.CompleteGraph(r)) for r in range(2,6)] [1, 3, 5, 6] See "The game chromatic index of wheels", Andres, Hochstättler, Schallück:: sage: [statistic(graphs.WheelGraph(r)) for r in range(2,7)] [1, 3, 5, 5, 6] sage: statistic(graphs.PetersenGraph()) """ G = G.relabel(immutable=True, inplace=False) if G.num_edges() == 0: return 0 for k in range(G.chromatic_index(), 2*max(G.degree())): if verbose: print k if Alice_wins(G, k, verbose=verbose): return k def normalize_colours(D): """ From left to right, use small colours first. """ pi = [None]*(max(D)+1) i = 0 for e in D: if e is not None and pi[e] is None: pi[e] = i i += 1 return tuple([None if e is None else pi[e] for e in D]) @cached_function def Alice_wins(G, k, C=None, E=None, verbose=False, indent=0): """Return whether C is a winning position for Alice, who wants to properly color the graph. Expect that the vertices are labelled 0,1,... """ def children(D): if all(c is None for c in D): colours = 1 else: colours = min(k, max(D)+2) for i in range(m): if D[i] is None: e = E[i] for d in range(colours): if not any(i != j and D[j] == d and (E[j][0] in e or E[j][1] in e) for j in range(m)): yield D[:i] + tuple([d]) + D[i+1:] if C is None: C = tuple([None]*G.num_edges()) if E is None: E = tuple(G.edges(labels=False)) m = len(E) uncoloured_edges = C.count(None) if uncoloured_edges == 0: return True if verbose: print " "*indent + "%s winning position?"%list(C) # let Alice colour an edge for A in children(C): # if C was missing precisely one edge, and we could # colour it, Alice wins if uncoloured_edges == 1: if verbose: print " "*indent + "yes" return True # Alice wins if there is a D such that all moves of Bob make Alice win has_colouring = False for B in children(A): has_colouring = True if not Alice_wins(G, k, normalize_colours(B), E, verbose=verbose, indent=indent+1): break else: if has_colouring: if verbose: print " "*indent + "yes" return True if verbose: print " "*indent + "no" return False ----------------------------------------------------------------------------- Statistic values: ([],1) => 0 ([],2) => 0 ([(0,1)],2) => 1 ([],3) => 0 ([(1,2)],3) => 1 ([(0,2),(1,2)],3) => 2 ([(0,1),(0,2),(1,2)],3) => 3 ([],4) => 0 ([(2,3)],4) => 1 ([(1,3),(2,3)],4) => 2 ([(1,2),(1,3),(2,3)],4) => 3 ([(0,3),(1,3),(2,3)],4) => 3 ([(0,3),(1,2)],4) => 1 ([(0,3),(1,2),(2,3)],4) => 2 ([(0,3),(1,2),(1,3),(2,3)],4) => 3 ([(0,2),(0,3),(1,2),(1,3)],4) => 3 ([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 3 ([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 5 ([],5) => 0 ([(3,4)],5) => 1 ([(2,4),(3,4)],5) => 2 ([(2,3),(2,4),(3,4)],5) => 3 ([(1,4),(2,4),(3,4)],5) => 3 ([(0,4),(1,4),(2,4),(3,4)],5) => 4 ([(1,4),(2,3)],5) => 1 ([(1,4),(2,3),(3,4)],5) => 2 ([(1,4),(2,3),(2,4),(3,4)],5) => 3 ([(1,3),(1,4),(2,3),(2,4)],5) => 3 ([(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 3 ([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 5 ([(0,1),(2,4),(3,4)],5) => 2 ([(0,4),(1,4),(2,3),(3,4)],5) => 3 ([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 4 ([(0,4),(1,3),(2,3),(2,4)],5) => 3 ([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 3 ([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 3 ([(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,3),(0,4),(1,2),(1,4),(2,3)],5) => 3 ([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 4 ([(0,3),(0,4),(1,2),(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) => 4 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 5 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 5 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 5 ([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 6 ([(0,1),(2,3),(2,4),(3,4)],5) => 3 ([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 3 ([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 4 ([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 4 ([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 4 ([],6) => 0 ([(4,5)],6) => 1 ([(3,5),(4,5)],6) => 2 ([(3,4),(3,5),(4,5)],6) => 3 ([(2,5),(3,5),(4,5)],6) => 3 ([(1,5),(2,5),(3,5),(4,5)],6) => 4 ([(0,5),(1,5),(2,5),(3,5),(4,5)],6) => 5 ([(2,5),(3,4)],6) => 1 ([(2,5),(3,4),(4,5)],6) => 2 ([(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(1,2),(3,5),(4,5)],6) => 2 ([(1,5),(2,5),(3,4),(4,5)],6) => 3 ([(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(1,5),(2,4),(3,4),(3,5)],6) => 3 ([(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 3 ([(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 3 ([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 3 ([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 4 ([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(1,2),(3,4),(3,5),(4,5)],6) => 3 ([(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 3 ([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4 ([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4 ([(0,1),(2,5),(3,5),(4,5)],6) => 3 ([(0,5),(1,5),(2,5),(3,4),(4,5)],6) => 4 ([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,5),(2,4),(3,4)],6) => 2 ([(0,5),(1,5),(2,4),(3,4),(4,5)],6) => 3 ([(0,5),(1,5),(2,3),(3,4),(4,5)],6) => 3 ([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,5),(2,3),(2,4),(3,4)],6) => 3 ([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 4 ([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6) => 4 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6) => 4 ([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6) => 3 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6) => 4 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 5 ([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,4),(2,3)],6) => 1 ([(0,1),(2,5),(3,4),(4,5)],6) => 2 ([(0,1),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 5 ([(0,1),(2,4),(2,5),(3,4),(3,5)],6) => 2 ([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 3 ([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6) => 3 ([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6) => 4 ([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 5 ([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6) => 4 ([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5 ([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 3 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,4),(2,3),(3,5),(4,5)],6) => 3 ([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,4),(2,3),(2,4),(3,5)],6) => 3 ([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 4 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6) => 3 ([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 4 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6) => 3 ([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6) => 4 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6) => 3 ([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6) => 4 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 4 ([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 6 ([(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) => 6 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 5 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6) => 6 ([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6) => 5 ([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6) => 4 ([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6) => 5 ([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6) => 3 ([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 4 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6) => 4 ([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6) => 4 ([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 5 ([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6) => 5 ([(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) => 6 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6) => 6 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6) => 6 ----------------------------------------------------------------------------- Created: Mar 15, 2018 at 22:20 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Mar 16, 2018 at 08:18 by Martin Rubey