Abstract view
The Thickness of the Cartesian Product of Two Graphs


Published:20160510
Printed: Dec 2016
Yichao Chen,
Department of Mathematics, Hunan University, 410082 Changsha, China
Xuluo Yin,
Department of Mathematics, Hunan University, 410082 Changsha, China
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$ which contains
no proper subgraph of thickness $t.$ In this paper, upper and
lower bounds are obtained for the thickness, $t(G\Box 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_{4k,4k},$ the thickness of the Cartesian product of
two complete bipartite graphs $K_{n,n}$ and $K_{n,n}$ is also
given, for $n\neq 4k+1$.