Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9514573 | Electronic Notes in Discrete Mathematics | 2005 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daphne Liu, Xuding Zhu,