Values
([],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
>>> Load all 208 entries. <<<
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!