The chromatic difference sequence of the Cartesian product of graphs

DOI10.1016/0012-365X(91)90150-ZMaRDI QIDQ810524zbMATH OpenFDO

Authors Huishan Zhou

Publication date 1991

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(91)90150-Z

zbMATH Keywords

chromatic difference sequenceproduct of graphsvertex colourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph theory (05C99)

Review text

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.

Recommendations

• The chromatic difference sequence of the Cartesian product of graphs. II
• Graph products and the chromatic difference sequence of vertex-transitive graphs
• Circulants and Sequences
• On colouring products of graphs
• On the ultimate normalized chromatic difference sequence of a graph

Cites work

• Homomorphisms of 3-chromatic graphs
• Point-symmetric graphs with a prime number of points
• Some partitions associated with a partially ordered set
• The chromatic difference sequence of a graph
• The structure of Sperner k-families

Cited in

(9)

• The chromatic difference sequence of the Cartesian product of graphs. II
• Independence ratios of graph powers
• Graph products and the chromatic difference sequence of vertex-transitive graphs
• On the ultimate independence ratio of a graph
• On the ultimate normalized chromatic difference sequence of a graph
• On the bounds for the ultimate independence ratio of a graph
• Chromatic difference sequences and homomorphisms
• scientific article; zbMATH DE number 5778120 (Why is no real title available?)
• Circulants and Sequences

This page was built for publication: The chromatic difference sequence of the Cartesian product of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q810524)