No label defined (Q3972003)

The outerthickness of a graph \(G\) is the minimum number of sets in a partition of \(E(G)\) such that each set induces an outerplanar graph. The outercoarseness of a graph \(G\) is the maximum number of sets in a partition of \(E(G)\) such that each set induces a non-outerplanar graph. Four results (some of which were announced without proof [\textit{R. K. Guy}, ``Outerthickness and outercoarseness of graphs'', Combinatorics, Proc. British combin. Conf., Aberystwyth 1973, 57--60 (1974; Zbl 0293.05108)]) are proved. Theorem 1. The outerthickness of \(K_n\) is \(\lceil(n+1)/4\rceil\), except that the outerthickness of \(K_7\) is 3. Theorem 2. The outerthickness of the \(n\)-cube is \(\lceil(n+1)/3\rceil\). Theorem 3. The outercoarseness of \(K_n\) is \(\lfloor n(n-1)/12\rfloor\). Theorem 4. The outercoarseness of the \(n\)-cube is between \((0.96n- 1.15)2^{n-4}\) and \(n2^{n-4}\) except that the lower bound may not hold for \(n=2, 5, 6\), and \(9\). Theorem 3 was first proved by \textit{L. W. Beineke} [The many facets of graph theory, Proc. Conf. Western Michigan Univ., Kalamazoo/Mi. 1968, 45--53 (1969; Zbl 0186.27601)]. [For the entire collection see Zbl 0698.00017.]