Strong products of -critical graphs
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)\).
- A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
- Cartesian graph factorization at logarithmic cost per edge
- Factoring a graph in polynomial time
- Finding the prime factors of strong direct product graphs in polynomial time
- scientific article; zbMATH DE number 3616459 (Why is no real title available?)
- Independence numbers of product graphs
- Isometric embeddings in Hamming graphs
- On a Problem of C. E. Shannon in Graph Theory
- On Factorable Extensions and Subgraphs of Prime Graphs
- On Isometric Embeddings of Graphs
- r-tuple colorings of uniquely colorable graphs
- Retract rigid Cartesian products of graphs
- Retracts of strong products of graphs
- Two remarks on retracts of graph products
- The independence number of the strong product of cycles
- Strong products of Kneser graphs
- On the chromatic number of the lexicographic product and the Cartesian sum of graphs
- Improved bounds for the chromatic number of the lexicographic product of graphs
- On the fractional chromatic number and the lexicographic product of graphs
- The chromatic numbers of graph bundles over cycles
- Coloring graph products---a survey
- The star chromatic numbers of graph products
- Strong product of factor-critical graphs
- Chromatic numbers of the strong product of odd cycles
- Clique-coloring numbers of some product graphs
- scientific article; zbMATH DE number 2230321 (Why is no real title available?)
- Acyclic coloring of products of digraphs
- The subset-strong product of graphs
- Colouring strong products
- Two remarks on retracts of graph products
This page was built for publication: Strong products of \(\chi\)-critical graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1801332)
