The chromatic difference sequence of the Cartesian product of graphs (Q810524)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The chromatic difference sequence of the Cartesian product of graphs |
scientific article |
Statements
The chromatic difference sequence of the Cartesian product of graphs (English)
0 references
1991
0 references
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.
0 references
vertex colourings
0 references
chromatic difference sequence
0 references
product of graphs
0 references