|
In graph theory, the (''a'', ''b'')-decomposability of an undirected graph is the existence of a partition of its edges into ''a'' + 1 sets, each one of them inducing a forest, except one who induces a graph with maximum degree ''b''. If this graph is also a forest, then we call this a F(''a'', ''b'')-decomposition. A graph with arboricity ''a'' is (''a'', 0)-decomposable. Every (''a'', ''0'')-decomposition or (''a'', ''1'')-decomposition is a F(''a'', ''0'')-decomposition or a F(''a'', ''1'')-decomposition respectively. == Graph Classes == * Every planar graph is F(2,4)-decomposable.〔, conjectured by . Improving results by then .〕 * Every planar graph with girth at least is * * F(2,0)-decomposable if .〔Implied by .〕 * * (1,4)-decomposable if . * * F(1,2)-decomposable if .〔Implied by , improving results by , then .〕 * * F(1,1)-decomposable if ,〔Independently proved by and implied by , improving results by for girth 11, then for girth 10 and for girth 9.〕 or if every cycle of is either a triangle or a cycle with at least 8 edges not belonging to a triangle.〔, even if not explicitly stated.〕 * * (1,5)-decomposable if has no 4-cycles.〔, improving results by , then .〕 * Every outerplanar graph is F(2,0)-decomposable〔 and (1,3)-decomposable.〔Proved without explicit reference by .〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「(a,b)-decomposability」の詳細全文を読む スポンサード リンク
|