location:  Publications → journals → CMB
Abstract view

# The Thickness of the Cartesian Product of Two Graphs

Published:2016-05-10
Printed: Dec 2016
• Yichao Chen,
Department of Mathematics, Hunan University, 410082 Changsha, China
• Xuluo Yin,
Department of Mathematics, Hunan University, 410082 Changsha, China
 Format: LaTeX MathJax PDF

## 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$.
 Keywords: planar graph, thickness, Cartesian product, $t$-minimal graph, complete bipartite graph
 MSC Classifications: 05C10 - Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25]

 top of page | contact us | privacy | site map |