×

Strong products of \(\chi\)-critical graphs. (English) Zbl 0787.05039

For a (finite, undirected, simple) graph \(G= (V(G),E(G))\), let \(\alpha(G)\), \(\omega(G)\), \(\chi(G)\) denote the independence number, clique number, chromatic number, respectively. The lexicographic product and the strong product of graphs \(G\) and \(H\) are denoted by \(G[H]\) and \(G\otimes H\), respectively, and the least integer \(\geq x\), \(x\in R\), by \(\lceil x\rceil\) (unfortunately, more than once also written as \([x]\) in the paper). The main result is that \[ \chi(G\otimes H)\leq \chi(G[H])\leq (\chi(G)- 1)\chi(H)+\left\lceil{\chi(H)\over \alpha(G)}\right\rceil \] holds for any graph \(H\) and any critical (with respect to vertex colouring) graph \(G\). As an interesting corollary it follows that if \(G\) has a retract which is critical and not complete, then \(\chi(G[H])<\chi(G)\chi(H)\) for every \(H\) with \(E(H)\neq\varnothing\). Furthermore, the main result is used to calculate the chromatic numbers for some strong products, namely \(\chi(\overline C_{2k+1}\otimes K_ n)= kn+\Bigl\lceil{n\over 2}\Bigr\rceil\) \((k\geq 2, n\geq 1)\), \(\chi(C_ 5\otimes C_ 5\otimes C_{2k+1})=10+\Bigl\lceil{5\over k}\Bigr\rceil\) \((k\geq 2)\), \(\chi((G+H)\otimes K_ n)=\chi(G\otimes K_ n)+\chi(H\otimes K_ n)\), \(\chi((K_{n-3}+ C_ 5)\otimes K_ m)= (n- 1)m+\Bigl\lceil{m\over 2}\Bigr\rceil\) \((n\geq 3, m\geq 1)\), where \(G+ H\), \(\overline G\), \(C_ n\) and \(K_ n\) denote the join of \(G\) and \(H\), the complement of \(G\), the cycle of length \(n\), and the complete graph on \(n\) vertices, respectively.
That the upper bound for \(\chi(G\otimes H)\) in \(\chi(G\otimes H)\leq \chi(G)\chi(H)\) cannot be improved for non-critical graphs \(G\) with \(\omega(G)<\chi(G)\) is shown by the construction of two sequences of graphs \(G^ k_ n\), \(n=1,2,\dots\), for \(k= 2\) and \(k= 4\) satisfying \(| V(G^ k_ n)|= (3k+ 2)n\), \(2= \omega(G^ k_ n)< \chi(G^ k_ n)= 3\), and \(\chi(G^ k_ n\otimes K_ k)= 3k= \chi(G^ k_ n)\chi(K_ k)\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Aurenhammer, F., Hagauer, J. and Imrich, W.,Factoring Cartesian-product graphs at logarithmic cost per edge. [Abeitsbericht 2/1990] Montanuniversität, Leoben, Austria. · Zbl 0770.68064
[2] Feigenbaum, J. andHaddad, R. W.,On factorable extensions and subgraphs of prime graphs. SIAM J. Discrete Math.2 (1989), 197–218. · Zbl 0736.05061 · doi:10.1137/0402017
[3] Feigenbaum, J., Hershberger, J. andSchäffer, A. A.,A polynomial time algorithm for finding the prime factors of a Cartesian-product graphs. Discrete Appl. Meth.12 (1985), 123–138. · Zbl 0579.68028 · doi:10.1016/0166-218X(85)90066-6
[4] Feigenbaum, J. andSchäffer, A. A.,Finding the prime factors of strong direct product graphs in polynomial time. Discrete Math.109 (1992), 77–102. · Zbl 0786.68076 · doi:10.1016/0012-365X(92)90280-S
[5] Geller, D.,r-tuple colorings of uniquely colorable graphs. Discrete Math.16 (1976), 9–12. · Zbl 0338.05104 · doi:10.1016/0012-365X(76)90089-3
[6] Geller, D. andStahl, S.,The chromatic number and other parameters of the lexicographic product. J. Combin. Theory Ser. B19 (1975), 87–95. · Zbl 0301.05108 · doi:10.1016/0095-8956(75)90076-3
[7] Graham, L. R. andWinkler, P. M.,On isometric embeddings of graphs. Trans. Amer. Math. Soc.288 (1985), 527–536. · Zbl 0576.05017 · doi:10.1090/S0002-9947-1985-0776391-5
[8] Hales, R. S.,Numerical invariants and the strong products of graphs. J. Combin. Theory Ser. B15 (1973), 146–155. · Zbl 0259.05111 · doi:10.1016/0095-8956(73)90014-2
[9] Imrich, W. andKlavžar, S.,Retracts of strong products of graphs. Discrete Math.109 (1992), 147–154. · Zbl 0780.05054 · doi:10.1016/0012-365X(92)90285-N
[10] Jha, P. K.,Hypercubes, median graphs and products of graphs: some algorithmic and combinatorial results. Ph.D. Thesis, Iowa State University, Ames, IA 1990.
[11] Klavžar, S.,Two remarks on retracts of graph products. Discrete Math.109 (1992), 155–160. · Zbl 0780.05055 · doi:10.1016/0012-365X(92)90286-O
[12] Klavžar, S. andMilutinović, U.,Strong products of Kneser’s graphs. Discrete Math., to appear.
[13] Nowakowski, R. andRival, I.,Retract rigid Cartesian products of graphs. Discrete Math.70 (1988), 169–184. · Zbl 0699.05047 · doi:10.1016/0012-365X(88)90091-X
[14] Rosenfeld, M.,On a problem of C. E. Shannon in graph theory. Proc. Amer. Math. Soc.18 (1967), 315–319. · Zbl 0147.42801 · doi:10.1090/S0002-9939-1967-0207590-3
[15] Sonnemann, E. andKrafft, O.,Independence numbers of product graphs. J. Combin. Theory Ser. B17 (1974), 133–142. · Zbl 0305.05113 · doi:10.1016/0095-8956(74)90081-1
[16] Stahl, S.,n-tuple colorings and associated graphs. J. Combin. Theory Ser. B20 (1976), 185–203. · Zbl 0316.05107 · doi:10.1016/0095-8956(76)90010-1
[17] Vesztergombi, K.,Some remarks on the chromatic number of the strong product of graphs. Acta Cybernet.4 (1978/79), 207–212. · Zbl 0397.05025
[18] Vesztergombi, K.,Chromatic number of strong product of graphs. In: Algebraic methods in graph theory, vol. I–II [Colloq. Math. Soc. János Bolyai, vol. 25]. North-Holland, Amsterdam–New York, 1981, pp. 819–825.
[19] Wilkeit, E.,Isometric embeddings in Hamming graphs. J. Combin. Theory Ser. B50 (1990), 179–197. · Zbl 0657.05023 · doi:10.1016/0095-8956(90)90073-9
[20] Winkler, P. M.,Factoring a graph in polynomial time. European J. Combin.8 (1987), 209–212. · Zbl 0625.05050
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.