Values
=>
Cc0020;cc-rep
([],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
([(0,3),(1,3),(2,3)],4)=>3
([(0,3),(1,2)],4)=>1
([(0,3),(1,2),(2,3)],4)=>2
([(1,2),(1,3),(2,3)],4)=>3
([(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
([(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
([(0,1),(2,4),(3,4)],5)=>2
([(2,3),(2,4),(3,4)],5)=>3
([(0,4),(1,4),(2,3),(3,4)],5)=>3
([(1,4),(2,3),(2,4),(3,4)],5)=>3
([(0,4),(1,4),(2,3),(2,4),(3,4)],5)=>4
([(1,3),(1,4),(2,3),(2,4)],5)=>3
([(0,4),(1,2),(1,3),(2,4),(3,4)],5)=>3
([(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>3
([(0,4),(1,3),(2,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,4),(1,3),(2,3),(2,4)],5)=>3
([(0,1),(2,3),(2,4),(3,4)],5)=>3
([(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)=>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,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5)=>4
([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>5
([(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),(3,4)],5)=>5
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5)=>4
([(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
([],6)=>0
([(4,5)],6)=>1
([(3,5),(4,5)],6)=>2
([(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
([(1,2),(3,5),(4,5)],6)=>2
([(3,4),(3,5),(4,5)],6)=>3
([(1,5),(2,5),(3,4),(4,5)],6)=>3
([(0,1),(2,5),(3,5),(4,5)],6)=>3
([(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,5),(3,4),(4,5)],6)=>4
([(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,5),(2,4),(3,4)],6)=>2
([(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,3),(3,4),(4,5)],6)=>3
([(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,4),(3,4),(4,5)],6)=>3
([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>4
([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>4
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>4
([(0,5),(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
([(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),(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,4),(2,3)],6)=>1
([(1,5),(2,4),(3,4),(3,5)],6)=>3
([(0,1),(2,5),(3,4),(4,5)],6)=>2
([(1,2),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(3,5),(4,5)],6)=>3
([(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(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
([(1,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
([(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>3
([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>4
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6)=>3
([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(1,4),(1,5),(2,3),(2,5),(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,5),(1,4),(2,3),(2,4),(3,5)],6)=>3
([(0,1),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,5),(2,3),(2,4),(3,4)],6)=>3
([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6)=>4
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>4
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6)=>4
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6)=>4
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,5),(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
([(0,5),(1,5),(2,3),(2,4),(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,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>5
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(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
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,5),(1,4),(1,5),(2,3),(2,4),(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,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>3
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>4
([(0,5),(1,3),(1,4),(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,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,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6)=>3
([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6)=>3
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>4
([(0,1),(0,2),(1,5),(2,4),(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,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>4
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,4),(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),(3,5),(4,5)],6)=>5
([(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,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6)=>4
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>5
([(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,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,5),(1,2),(1,3),(1,4),(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,4),(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,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,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),(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,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>6
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6)=>3
([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,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,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>6
([(0,3),(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),(2,3),(4,5)],6)=>3
([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6)=>4
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6)=>4
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>5
([(0,1),(1,5),(2,3),(2,4),(2,5),(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,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6)=>4
([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(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,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,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,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,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6)=>4
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>5
([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>4
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>6
([(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,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(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),(4,5)],6)=>6
([(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),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(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,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>6
([(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),(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,4),(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,3),(1,4),(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,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>6
([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(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
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
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.
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
[2] Andres, S. D., Hochstättler, W., Schallück, C. The game chromatic index of wheels MathSciNet:2825608
Code
def statistic(G):
"""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 Alice_wins(G, k):
return k
def normalize_colours(D):
"""
From left to right, use small colours first.
"""
pi = [None]*(max([v for v in D if v is not None])+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):
"""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(v for v in D if v is not None)+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
# 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:
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):
break
else:
if has_colouring:
return True
return False
Created
Mar 15, 2018 at 22:20 by Martin Rubey
Updated
Dec 17, 2020 at 18:05 by Martin Rubey
searching the database
Sorry, this statistic was not found in the database
or
add this statistic to the database – it's very simple and we need your support!