Remarks on the thickness of Kn, n, n

Yan Yang


The thickness θ(G) of a graph G is the minimum number of planar subgraphs into which G can be decomposed. In this paper, we provide a new upper bound for the thickness of the complete tripartite graphs Kn, n, n (n ≥ 3) and obtain θ(Kn, n, n) = ⌈(n + 1) / 3⌉, when n ≡ 3 (mod 6).


Thickness, complete tripartite graph, planar subgraphs 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