Plane triangulations are 6-partitionable (Q1849915): Difference between revisions

Let \(G=(V,E)\) be a graph with \(n\) vertices. Let \(n=n_1 + n_2 + \cdots + n_k\) be an ordered partition of \(n\) into \(k\) parts, \(n_i \geq 1\) and \(1 \leq i \leq k \leq n\). A \(k\)-partition of \(G\) is a partition of \(V\) into \(k\) parts \(P_1, P_2, \ldots, P_k\) such that \(|P_i|=n_i\) and \(P_i\) induces a connected subgraph of \(G\) for all \(i\), \(1\leq i \leq k\). We say that \(G\) is \(k\)-partitionable if there exists a \(k\)-partition of \(G\) for every partition of \(n\) into \(k\) parts. \textit{L. Lovász} [Acta Math. Acad. Sci. Hung. 30, 241-251 (1978; Zbl 0403.05040)] showed that \(k\)-connected graphs are \(k\)-partititonable. The authors of the present paper prove that plane triangulations are \(6\)-partitionable and there exist non-\(7\)-partitionable plane triangulations.