Plane triangulations are 6-partitionable (Q1849915): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(01)00463-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2086459036 / rank | |||
Normal rank |
Latest revision as of 09:44, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Plane triangulations are 6-partitionable |
scientific article |
Statements
Plane triangulations are 6-partitionable (English)
0 references
2 December 2002
0 references
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.
0 references
partitionable
0 references
plane triangulation
0 references