Values
=>
Cc0020;cc-rep
([],1)=>1
([],2)=>2
([(0,1)],2)=>1
([],3)=>2
([(1,2)],3)=>2
([(0,2),(1,2)],3)=>2
([(0,1),(0,2),(1,2)],3)=>1
([],4)=>2
([(2,3)],4)=>3
([(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)=>3
([(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)=>2
([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>1
([],5)=>2
([(3,4)],5)=>3
([(2,4),(3,4)],5)=>3
([(1,4),(2,4),(3,4)],5)=>2
([(0,4),(1,4),(2,4),(3,4)],5)=>2
([(1,4),(2,3)],5)=>3
([(1,4),(2,3),(3,4)],5)=>3
([(0,1),(2,4),(3,4)],5)=>3
([(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)=>3
([(1,3),(1,4),(2,3),(2,4)],5)=>2
([(0,4),(1,2),(1,3),(2,4),(3,4)],5)=>2
([(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>3
([(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>2
([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5)=>2
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,4),(1,3),(2,3),(2,4)],5)=>2
([(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)=>2
([(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)=>2
([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(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)=>4
([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>3
([(0,3),(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)],5)=>2
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5)=>2
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1
([],6)=>2
([(4,5)],6)=>3
([(3,5),(4,5)],6)=>3
([(2,5),(3,5),(4,5)],6)=>3
([(1,5),(2,5),(3,5),(4,5)],6)=>2
([(0,5),(1,5),(2,5),(3,5),(4,5)],6)=>2
([(2,5),(3,4)],6)=>3
([(2,5),(3,4),(4,5)],6)=>3
([(1,2),(3,5),(4,5)],6)=>3
([(3,4),(3,5),(4,5)],6)=>4
([(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)=>3
([(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,5),(2,4),(3,4)],6)=>3
([(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)=>3
([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,4),(2,3)],6)=>3
([(1,5),(2,4),(3,4),(3,5)],6)=>3
([(0,1),(2,5),(3,4),(4,5)],6)=>3
([(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)=>3
([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(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)=>3
([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(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)=>3
([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(2,4),(3,5)],6)=>3
([(0,1),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,5),(2,3),(2,4),(3,4)],6)=>4
([(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)=>3
([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,5),(1,5),(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)=>4
([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(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)=>3
([(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)=>3
([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(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)=>3
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6)=>2
([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6)=>2
([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>2
([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6)=>2
([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2
([(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)=>2
([(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)=>3
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6)=>3
([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6)=>3
([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>3
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>2
([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(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)=>2
([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3
([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5
([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4
([(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)=>3
([(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)=>2
([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>2
([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3
([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2
([(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)=>2
([(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)=>2
([(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)=>2
([(0,2),(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)=>2
([(0,1),(0,2),(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)=>1
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 Prague dimension of a graph.
This is the least number of complete graphs such that the graph is an induced subgraph of their (categorical) product.
Put differently, this is the least number $n$ such that the graph can be embedded into $\mathbb N^n$, where two points are connected by an edge if and only if they differ in all coordinates.
This is the least number of complete graphs such that the graph is an induced subgraph of their (categorical) product.
Put differently, this is the least number $n$ such that the graph can be embedded into $\mathbb N^n$, where two points are connected by an edge if and only if they differ in all coordinates.
References
[1] Lovász, L., Nešetřil, J., Pultr, A. On a product dimension of graphs MathSciNet:0584160
Code
def statistic(G, fast=True):
"""
Proposition 2.3 of Lovász, László, J. Nešetšil, and Ales
Pultr. "On a product dimension of graphs." Journal of
Combinatorial Theory, Series B 29.1 (1980): 47-67.::
sage: N = 7; l = [G for n in range(1, N) for G in graphs(n) if G.complement().chromatic_index() <= 1]
sage: all(statistic(G) == G.complement().chromatic_index() + 1 for G in l)
True
sage: N = 6; l = [G for n in range(1, N) for G in graphs(n) if G.complement().chromatic_index() > 1]
sage: all(statistic(G) <= G.complement().chromatic_index() for G in l)
True
sage: all(statistic(G) == G.complement().chromatic_index() for G in l if G.complement().is_triangle_free())
True
Proposition 3.6::
sage: N = 8; l = [(k, n, graphs.CompleteGraph(n) + Graph(k)) for k in range(1, N) for n in range(2, N)]
sage: all(statistic(G) == (n+1 if k > factorial(n-1) else n) for k, n, G in l)
True
TESTS::
sage: N = 6; all(statistic(G) == statistic(G, False) for n in range(N) for G in graphs(n))
True
"""
if fast:
Gc = G.complement()
Gc_chi = Gc.chromatic_index()
if Gc_chi <= 1:
return Gc_chi + 1
if Gc.is_triangle_free():
return Gc_chi
lG = sorted(G.connected_components_subgraphs(), key=lambda G: G.num_verts())
if len(lG) > 1 and lG[-2].num_verts() == 1 and lG[-1].is_clique():
if len(lG) - 1 <= factorial(lG[-1].num_verts()-1):
return lG[-1].num_verts()
return lG[-1].num_verts() + 1
d = 0
n = G.num_verts()
K = graphs.CompleteGraph(n)
H = K
while True:
d += 1
if H.subgraph_search(G, induced=True) is not None:
return d
H = H.categorical_product(K)
Created
Nov 19, 2020 at 10:35 by Martin Rubey
Updated
Nov 19, 2020 at 15:52 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!