Coloring the Cartesian Sum of Graphs

For graphs G and H, let G⊕H denote their Cartesian sum. We prove that for any graphs G and H, χ(G⊕H)⩽max{⌈χc(G)χ(H)⌉, ⌈χ(G)χc(H)⌉}. Moreover the bound is sharp. We conjecture that for any graphs G and H, χc(G⊕H)⩽max{χ(H)χc(G), χ(G)χc(H)}. The conjectured bound would be sharp if it is true. We confirm this conjecture for graphs G and H with special values of χc(G) and χc(H). These results improve previously known bounds on the chromatic number and the circular chromatic number for the Cartesian sum of graphs.