The authors investigate the chromatic number \(\chi\) and the circular chromatic number \(\chi_c\) of the Cartesian sum \(G\oplus H\) of two graphs \(G\) and \(H\). They prove that \[ \chi(G\oplus H)\leq \max\left(\lceil\chi_c(G)\chi(H)\rceil, \lceil\chi_c(H)\chi(G)\rceil\right) \] holds in general and that \[ \chi_c(G\oplus H)\leq \chi_c(G)\chi(H) \] holds under specific assumptions for the values of \(\chi_c(G)\) and \(\chi_c(H)\).
Recommendations
- On sum coloring of graphs
- Coloring sums of extensions of certain graphs
- Sum coloring on certain classes of graphs
- Sum Multicoloring of Graphs
- Sum-defined colorings in graphs
- Generalised colouring sums of graphs
- The coloring of graphs
- TOTAL COLORING OF CERTAIN GRAPHS
- scientific article; zbMATH DE number 4134070
- Total Colourings of Graphs
Cites work
- A note on the star chromatic number
- A survey on Hedetniemi's conjecture
- Chromatic Number of Cartesian Sum of Two Graphs
- Circular chromatic number: A survey
- Coloring graph products---a survey
- Fractional colorings with large denominators
- Hedetniemi's conjecture---a survey
- scientific article; zbMATH DE number 3172309 (Why is no real title available?)
- scientific article; zbMATH DE number 1131873 (Why is no real title available?)
- scientific article; zbMATH DE number 2151258 (Why is no real title available?)
- scientific article; zbMATH DE number 2119454 (Why is no real title available?)
- Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
- On chromatic number of products of two graphs
- On the chromatic number of the lexicographic product and the Cartesian sum of graphs
- Recent developments in circular colouring of graphs
- Star chromatic number
- Star chromatic numbers and products of graphs
- Star chromatic numbers of graphs
- Star Extremal Circulant Graphs
- Star-extremal graphs and the lexicographic product
- The chromatic number of the product of two 4-chromatic graphs is 4
- The fractional chromatic number of infinite graphs
- The fractional chromatic number of the direct product of graphs
Cited in
(8)- On the chromatic number of the lexicographic product and the Cartesian sum of graphs
- Gromov hyperbolicity in the Cartesian sum of graphs
- Chromatic number via Turán number
- STACS 2004
- Results on hyperbolicity in graphs: a survey
- scientific article; zbMATH DE number 7655724 (Why is no real title available?)
- On automorphisms and fixing number of co-normal product of graphs
- Bounds on the domination number and the metric dimension of co-normal product of graphs
This page was built for publication: Coloring the Cartesian sum of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q998323)
