| |
| The thickness t(G) of a graph G is the minimum number of planar spanning subgraphsinto which G can be decomposed. Determining the thickness of a graphis NP-hard, thus it is very difficult to obtain the exact number of thickness forarbitrary graphs. Compared with other classical topological invariant, the results about thickness are few. For the thickness of complete bipartite graph $K_{m,n}$, Beineke, Harary and Moon obtained the following formula in 1964 ,$$t(K_{m,n})=leftlceil rac{mn}{2(m+n-2)}
ight
ceil,$$ except possibly when $m$ and $n$ are both odd and there exists an integer $k$ satisfying $n=leftlfloor rac{2k(m-2)}{(m-2k)}
ight
floor$.According to the above formula, the thickness of the complete bipartite graph is not completely determined. In 1980, two famous graph theorist Gross and Harary posed the following problem in the paper 《 Some problems in topological graph theory》： Find the thickness of $K_{m,n}$ for all $m,n?$ In this paper, we obtain the thickness for the complete bipartite graph $K_{n,n+4} .$ |
|
| Keywords:graph; graph thickness; complete bipartite graph; complete tripartite graph |
|
