Coloring the Cartesian sum of graphs
type: Item
instance of: scholarly article
title: Coloring the Cartesian sum of graphs
zbMATH Open document ID: 1165.05009
author: Daphne Der-Fen Liu
author: Xuding Zhu
published in: Discrete Mathematics
publication date: 2009-01-28T00:00:00Z
review text: 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)\).
reviewed by: Markus Fulmek
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5499734
zbMATH Keywords: Cartesian sum of graphs
zbMATH Keywords: chromatic number
zbMATH Keywords: circular chromatic number
MaRDI profile type: Publication
full work available at URL: j.disc.2007.11.005
OpenAlex ID: W2175192782
cites work: A note on the star chromatic number
cites work: On chromatic number of products of two graphs
cites work: On the chromatic number of the lexicographic product and the Cartesian sum of graphs
cites work: The chromatic number of the product of two 4-chromatic graphs is 4
cites work: Fractional colorings with large denominators
cites work: Star-extremal graphs and the lexicographic product
cites work: The fractional chromatic number of infinite graphs
cites work: Star Extremal Circulant Graphs
cites work: Coloring graph products---a survey
cites work: Q3291034
cites work: Hedetniemi's conjecture---a survey
cites work: Q4382863
cites work: Star chromatic numbers of graphs
cites work: Q4828856
cites work: Q4660728
cites work: Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
cites work: Chromatic Number of Cartesian Sum of Two Graphs
cites work: Star chromatic number
cites work: The fractional chromatic number of the direct product of graphs
cites work: Star chromatic numbers and products of graphs
cites work: Circular chromatic number: A survey
cites work: Q3424895
cites work: A survey on Hedetniemi's conjecture
DOI: 10.1016/J.DISC.2007.11.005
Recommended article: On sum coloring of graphs
Recommended article: Coloring Sums of Extensions of Certain Graphs
Recommended article: Q5488889
Recommended article: Sum Multicoloring of Graphs
Recommended article: Q4559904
Recommended article: Generalised colouring sums of graphs
Recommended article: The coloring of graphs
Recommended article: TOTAL COLORING OF CERTAIN GRAPHS
Recommended article: Q3035308
Recommended article: Total Colourings of Graphs
description: scientific article; zbMATH DE number 5499734