Coloring the Cartesian sum of graphs (Q998323)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Coloring the Cartesian sum of graphs
scientific article

    Statements

    Coloring the Cartesian sum of graphs (English)
    0 references
    0 references
    0 references
    28 January 2009
    0 references
    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)\).
    0 references
    0 references
    Cartesian sum of graphs
    0 references
    chromatic number
    0 references
    circular chromatic number
    0 references

    Identifiers