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
    0 references

    Identifiers