A note on the thickness of some complete bipartite graphs
Abstract
The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. Determining the thickness for the complete bipartite graph is an unsolved problem in graph theory for over fifty years. Using a new planar decomposition for K4k − 4, 4k (k ≥ 4), we obtain the thickness of the complete bipartite graph Kn, n + 4, for n ≥ 1.
Keywords
Planar graph, thickness, complete bipartite graph
DOI: https://doi.org/10.26493/1855-3974.1236.4d7
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