Alles, Peter The dimension of sums of graphs. (English) Zbl 0581.05048 Discrete Math. 54, 229-233 (1985). The dimension of a graph G (dim G) is the least natural number n such that G is an induced subgraph of a direct product of n graphs. The author obtains an improvement on the upper bound obtained by S. Poljak and V. Rödl [Czechosl. Math. J. 30, 475-485 (1980; Zbl 0456.05051)] on the dimension of sums of graphs. The following are the main results: (1) If n is a power of a prime, then, for m,\(\ell \in N\), \(\dim n^{\ell}K_ n\leq 1+\ell (n-1)\) and \(\dim m K_ n\leq 1+(n-1)\lceil \log^ m_ n\rceil\). (2) Let \(G_ 1,G_ 2,...,G_ m\) be arbitrary graphs, and \(d=\max \{\dim G_ i| \quad 1\leq i\leq m\}\) and \(n=\max \{\chi (G_ i)| \quad 1\leq i\leq m\},\) where \(\chi\) is the chromatic number. Then \(\dim \sum^{m}_{i=1}G_ i\leq d+1+(n-1)\lceil \log^ m_{\underline n}\rceil,\) where ṉ is the least (or any) prime power greater than or equal to n. The proof technique employed is a new concept of matrices with covering property which is a sort of generalization of orthogonal Latin squares. Reviewer: K.R.Parthasarathy Cited in 1 ReviewCited in 2 Documents MSC: 05C75 Structural characterization of families of graphs 05C15 Coloring of graphs and hypergraphs 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C35 Extremal problems in graph theory 05B15 Orthogonal arrays, Latin squares, Room squares Keywords:orthogonal partitions; dimension; direct product; sums of graphs; chromatic number; matrices; Latin squares Citations:Zbl 0456.05051 PDFBibTeX XMLCite \textit{P. Alles}, Discrete Math. 54, 229--233 (1985; Zbl 0581.05048) Full Text: DOI References: [1] Alles, P., Estimation of the dimension of some types of graph by means of orthogonal latin squares, Preprint-Nr. 749, TH Darmstadt (1983) [2] Hall, M., Combinatorial Theory (1967), Blaisdell: Blaisdell Waltham · Zbl 0196.02401 [3] Křivka, P., Dimension of the sum of two copies of a graph, Czechoslovak Math. J., 31, 514-520 (1981) · Zbl 0484.05053 [4] Lovász, L.; Nešetřil, J.; Pultr, A., On a product dimension of graphs, J. Combin. Theory Ser. B, 29, 47-67 (1980) · Zbl 0439.05038 [5] Nešetřil, J.; Pultr, A., A Dushnik-Miller type dimension of graphs and its complexity, (Lecture Notes in Computer Science, 50 (1977), Springer: Springer Berlin), 482-493 · Zbl 0362.05073 [6] Nešetřil, J.; Pultr, A., Product and other representations of graphs and related characteristics, (Coll. Math. Soc. J. Bolyai, 25 (1981), North-Holland: North-Holland Amsterdam), 571-598 [7] Poljak, S.; Pultr, A., Representing graphs by means of strong and weak products, Comment. Math. Univ. Carolinae, 22, 449-465 (1981) · Zbl 0476.05074 [8] Poljak, S.; Rödl, V., Orthogonal partitions and covering of graphs, Czechoslovak Math. J., 30, 475-485 (1980) · Zbl 0456.05051 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.