The Thickness of the Cartesian Product of Two Graphs
Yichao Chen, Xuluo Yin · Canadian Mathematical Bulletin · 2016
Abstract The thickness of a graph G is the minimum number of planar subgraphs whose union is G . A t -minimal graph is a graph of thickness t that contains no proper subgraph of thickness t . In this paper, upper and lower bounds are obtained for the thickness, t ( G ⎕ H ), of the Cartesian product of two graphs G and H , in terms of the thickness t ( G ) and t ( H ). Furthermore, the thickness of the Cartesian product of two planar graphs and of a t -minimal graph and a planar graph are determined. By using a new planar decomposition of the complete bipartite graph K 4 k ,4 k , the thickness of the Cartesian product of two complete bipartite graphs K n , n and K n , n is also given for n ≠4 k + 1.