***************************************************************************** * 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: St001642 ----------------------------------------------------------------------------- Collection: Graphs ----------------------------------------------------------------------------- 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. ----------------------------------------------------------------------------- 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) ----------------------------------------------------------------------------- Statistic 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 ([(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 ----------------------------------------------------------------------------- Created: Nov 19, 2020 at 10:35 by Martin Rubey ----------------------------------------------------------------------------- Last Updated: Nov 19, 2020 at 15:52 by Martin Rubey