A note on the thickness of some complete bipartite graphs

Siwei Hu, Yichao Chen

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

Full Text:

PDF ABSTRACTS (EN/SI)


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