The thickness of the Kronecker product of graphs

Xia Guo, Yan Yang


The thickness of a graph G is the minimum number of planar subgraphs whose union is G. In this paper, we present sharp lower and upper bounds for the thickness of the Kronecker product G × H of two graphs G and H. We also give the exact thickness numbers for the Kronecker product graphs Kn × K2, Km, n × K2 and Kn, n, n × K2.


Thickness, Kronecker product graph, planar decomposition

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications