The chromatic difference sequence of the Cartesian product of graphs (Q810524)

In this paper vertex colourings of simple undirected graphs G are considered. The chromatic difference sequence cds(G) of G is defined by \[ cds(G)=(a(1),a(2),...), \] where \(\sum^{t}_{j=1}a(j)\) is the maximum number of vertices in an induced t-colourable subgraph of G for \(t=1,2,..\).. Four main results are obtained: the chromatic difference sequence (cds) of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.