Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree. Issue 4 (3rd January 2013)

• Record Type: Journal Article
• Authors: Kim, Seog‐Jin; Kostochka, Alexandr V.; West, Douglas B.; Wu, Hehui; Zhu, Xuding
• Is Part Of: Journal of graph theory. Volume 74:Issue 4(2013)
• Page Start: 369
• Page End: 391
• Publication Date: 2013-01-03
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21711
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>For a loopless multigraph <italic>G</italic>, the <italic>fractional arboricity</italic> Arb(<italic>G</italic>) is the maximum of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62f5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mfrac><mml:mrow><mml:mo>|</mml:mo><mml:mi>E</mml:mi><mml:mo>(</mml:mo><mml:mi>H</mml:mi><mml:mo>)</mml:mo><mml:mo>|</mml:mo></mml:mrow><mml:mrow><mml:mo>|</mml:mo><mml:mi>V</mml:mi><mml:mo>(</mml:mo><mml:mi>H</mml:mi><mml:mo>)</mml:mo><mml:mo>|</mml:mo><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac></mml:math></alternatives> over all subgraphs <italic>H</italic> with at least two vertices. Generalizing the Nash‐Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62gq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi> Arb </mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≤</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mfrac><mml:mi>d</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>d</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac></mml:mrow></mml:math></alternatives>, then <italic>G</italic> decomposes into <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62h8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives> forests with one having maximum degree at most <italic>d</italic>. The conjecture was previously proved for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62kc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>, </mml:mo><mml:mi>d</mml:mi><mml:mo>)</mml:mo><mml:mo>∈</mml:mo><mml:mo>{</mml:mo><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>, </mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo><mml:mo>, </mml:mo><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>, </mml:mo><mml:mn>2</mml:mn><mml:mo>)</mml:mo><mml:mo>}</mml:mo></mml:mrow></mml:math></alternatives>; we prove it for <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62ng" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>=</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives> and when <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62p1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives> and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62r4" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>≤</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives>. For <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62vs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>, </mml:mo><mml:mi>d</mml:mi><mml:mo>)</mml:mo><mml:mo>=</mml:mo><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>, </mml:mo><mml:mn>2</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives>, we can further restrict one forest to have at most two edges in each component.</p> <p>For general <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n62xw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>k</mml:mi><mml:mo>, </mml:mo><mml:mi>d</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives>, we prove weaker conclusions. If <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n64h9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>></mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:math></alternatives>, then <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n63jb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi> Arb </mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≤</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mfrac><mml:mi>d</mml:mi><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mi>d</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:mfrac></mml:mrow></mml:math></alternatives> implies that <italic>G</italic> decomposes into <italic>k</italic> forests plus a multigraph (not necessarily a forest) with maximum degree at most <italic>d</italic>. If <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n63kw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>≤</mml:mo><mml:mi>k</mml:mi></mml:mrow></mml:math></alternatives>, then <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n63g7" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi> Arb </mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>≤</mml:mo><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mfrac><mml:mi>d</mml:mi><mml:mrow><mml:mn>2</mml:mn><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:mrow></mml:math></alternatives> implies that <italic>G</italic> decomposes into <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg3t1n63hs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21711:jgt21711-math-0014" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math></alternatives> forests, one having maximum degree at most <italic>d</italic>. Our results generalize earlier results about decomposition of sparse planar graphs.</p> </abstract>