请输入您要查询的百科知识：

　

词条 (a, b)-decomposition
释义

  1. Graph classes

  2. Notes

  3. References (chronological order)

{{DISPLAYTITLE:(a, b)-decomposition}}

In graph theory, the (a, b)-decomposition of an undirected graph is a partition of its edges into a + 1 sets, each one of them inducing a forest, except one which 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.[1]
  • Every planar graph with girth at least is
    • F(2, 0)-decomposable if .[2]
    • (1, 4)-decomposable if .[3]
    • F(1, 2)-decomposable if .[4]
    • F(1, 1)-decomposable if ,[5] or if every cycle of is either a triangle or a cycle with at least 8 edges not belonging to a triangle.[6]
    • (1, 5)-decomposable if has no 4-cycles.[7]
  • Every outerplanar graph is F(2, 0)-decomposable[2] and (1, 3)-decomposable.[8]

Notes

1. ^{{harvtxt|Gonçalves|2009}}, conjectured by {{harvtxt|Balogh et al.|2005}}. Improving results by {{harvtxt|Nash-Williams|1964}} then {{harvtxt|Balogh et al.|2005}}.
2. ^1 Implied by {{harvtxt|Nash-Williams|1964}}.
3. ^{{harvtxt|He et al.|2002}}
4. ^Implied by {{harvtxt|Montassier et al.|2012}}, improving results by {{harvtxt|He et al.|2002}}, then {{harvtxt|Kleitman|2008}}.
5. ^Independently proved by {{harvtxt|Wang|Zhang|2011}} and implied by {{harvtxt|Montassier et al.|2012}}, improving results by {{harvtxt|He et al.|2002}} for girth 11, then {{harvtxt|Bassa et al.|2010}} for girth 10 and {{harvtxt|Borodin et al.|2008a}} for girth 9.
6. ^{{harvtxt|Borodin et al.|2009b}}, even if not explicitly stated.
7. ^{{harvtxt|Borodin et al.|2009a}}, improving results by {{harvtxt|He et al.|2002}}, then {{harvtxt|Borodin et al.|2008b}}.
8. ^Proved without explicit reference by {{harvtxt|Guan|Zhu|1999}}.

References (chronological order)

{{refbegin}}
  • {{cite journal|last=Nash-Williams|first=Crispin St. John Alvah|title=Decomposition of finite graphs into forests|journal=Journal of the London Mathematical Society|volume=39|issue=1|year=1964|pages=12|doi=10.1112/jlms/s1-39.1.12|mr=0161333|ref=harv}}
  • {{cite journal

| last = Guan
| first = D. J.
| last2 = Zhu
| first2 = Xuding
| date = 1999
| title = Game chromatic number of outerplanar graphs
| journal = Journal of Graph Theory
| volume = 30
| issue = 1
| pages = 67–70
| ref = harv
| doi=10.1002/(sici)1097-0118(199901)30:1<67::aid-jgt7>3.0.co;2-m
}}
  • {{cite journal

| last = He
| first = Wenjie
| last2 = Hou
| first2 = Xiaoling
| last3 = Lih
| first3 = Ko-Wei
| last4 = Shao
| first4 = Jiating
| last5 = Wang
| first5 = Weifan
| last6 = Zhu
| first6 = Xuding
| date = 2002
| title = Edge-partitions of planar graphs and their game coloring numbers
| journal = Journal of Graph Theory
| volume = 41
| issue = 4
| pages = 307–311
| ref = {{harvid|He et al.|2002}}
| doi = 10.1002/jgt.10069
}}
  • {{cite journal

| last = Balogh
| first = József
| last2 = Kochol
| first2 = Martin
| last3 = Pluhár
| first3 = András
| last4 = Yu
| first4 = Xingxing
| date = 2005
| title = Covering planar graphs with forests
| url = http://www.sciencedirect.com/science/article/pii/S0095895604001273
| journal = Journal of Combinatorial Theory, Series B
| volume = 94
| issue = 1
| pages = 147–158
| ref = {{harvid|Balogh et al.|2005}}
| doi = 10.1016/j.ejc.2007.06.020
}}
  • {{cite journal

| last = Borodin
| first = Oleg V.
| last2 = Kostochka
| first2 = Alexandr V.
| last3 = Sheikh
| first3 = Naeem N.
| last4 = Yu
| first4 = Gexin
| date = 2008
| title = Decomposing a planar graph with girth 9 into a forest and a matching
| url = http://www.sciencedirect.com/science/article/pii/S0195669807001151
| journal = European Journal of Combinatorics
| volume = 29
| issue = 5
| pages = 1235–1241
| ref = {{harvid|Borodin et al.|2008a}}
| doi = 10.1016/j.ejc.2007.06.020
}}
  • {{cite journal

| last = Borodin
| first = Oleg V.
| last2 = Kostochka
| first2 = Alexandr V.
| last3 = Sheikh
| first3 = Naeem N.
| last4 = Yu
| first4 = Gexin
| date = 2008
| title = M-Degrees of Quadrangle-Free Planar Graphs
| url = http://www.math.uiuc.edu/~kostochk/docs/2012/jgt09bsy.pdf
| journal = Journal of Graph Theory
| volume = 60
| issue = 1
| pages = 80–85
| ref = {{harvid|Borodin et al.|2008b}}
| doi = 10.1002/jgt.20346
| citeseerx = 10.1.1.224.8397
}}
  • {{cite journal

| last = Kleitman
| first = Daniel J.
| date = 2008
| title = Partitioning the Edges of a Girth 6 Planar Graph into those of a Forest and those of a Set of Disjoint Paths and Cycles
| journal = Manuscript
| ref = harv
}}
  • {{cite journal

| last = Gonçalves
| first = Daniel
| date = 2009
| title = Covering planar graphs with forests, one having bounded maximum degree
| url = http://www.sciencedirect.com/science/article/pii/S0095895608000774
| journal = Journal of Combinatorial Theory, Series B
| volume = 99
| issue = 2
| pages = 314–322
| ref = harv
| doi = 10.1016/j.jctb.2008.07.004
}}
  • {{cite journal

| last = Borodin
| first = Oleg V.
| last2 = Ivanova
| first2 = Anna O.
| last3 = Kostochka
| first3 = Alexandr V.
| last4 = Sheikh
| first4 = Naeem N.
| date = 2009
| title = Decompositions of Quadrangle-Free Planar Graphs
| url = http://www.math.uiuc.edu/~kostochk/docs/2012/dmgt09bis.pdf
| journal = Discussiones Mathematicae Graph Theory
| volume = 29
| pages = 87–99
| ref = {{harvid|Borodin et al.|2009a}}
| doi=10.7151/dmgt.1434
| citeseerx = 10.1.1.224.8787
}}
  • {{cite journal

| last = Borodin
| first = Oleg V.
| last2 = Ivanova
| first2 = Anna O.
| last3 = Kostochka
| first3 = Alexandr V.
| last4 = Sheikh
| first4 = Naeem N.
| date = 2009
| title = Planar graphs decomposable into a forest and a matching
| url = http://www.sciencedirect.com/science/article/pii/S0012365X07010771
| journal = Discrete Mathematics
| volume = 309
| issue = 1
| pages = 277–279
| ref = {{harvid|Borodin et al.|2009b}}
| doi=10.1016/j.disc.2007.12.104
}}
  • {{cite journal

| last = Bassa
| first = A.
| last2 = Burns
| first2 = J.
| last3 = Campbell
| first3 = J.
| last4 = Deshpande
| first4 = A.
| last5 = Farley
| first5 = J.
| last6 = Halsey
| first6 = L.
| last7 = Ho
| first7 = S.-Y.
| last8 = Kleitman
| first8 = D.
| last9 = Michalakis
| first9 = S.
| last10 = Persson
| first10 = P.-O.
| last11 = Pylyavskyy
| first11 = P.
| last12 = Rademacher
| first12 = L.
| last13 = Riehl
| first13 = A.
| last14 = Rios
| first14 = M.
| last15 = Samuel
| first15 = J.
| last16 = Tenner
| first16 = B.E.
| last17 = Vijayasarathy
| first17 = A.
| last18 = Zhao
| first18 = L.
| date = 2010
| title = Partitioning a Planar Graph of Girth 10 into a Forest and a Matching
| journal = European Journal of Combinatorics
| volume = 124
| issue = 3
| pages = 213–228
| ref = {{harvid|Bassa et al.|2010}}
| doi = 10.1111/j.1467-9590.2009.00468.x
}}
  • {{cite journal

| last = Wang
| first = Yingqian
| last2 = Zhang
| first2 = Qijun
| date = 2011
| title = Decomposing a planar graph with girth at least 8 into a forest and a matching
| url = http://www.sciencedirect.com/science/article/pii/S0012365X1100029X
| journal = Discrete Mathematics
| volume = 311
| issue = 10–11
| pages = 844–849
| ref = harv
| doi = 10.1016/j.disc.2011.01.019
}}
  • {{cite journal

| last = Montassier
| first = Mickaël
| last2 = Ossona de Mendez
| first2 = Patrice | author2-link = Patrice Ossona de Mendez
| last3 = André
| first3 = Raspaud
| last4 = Zhu
| first4 = Xuding
| date = 2012
| title = Decomposing a graph into forests
| url = http://www.sciencedirect.com/science/article/pii/S0095895611000438
| journal = Journal of Combinatorial Theory, Series B
| volume = 102
| issue = 1
| pages = 38–52
| ref = {{harvid|Montassier et al.|2012}}
| doi = 10.1016/j.jctb.2011.04.001
}}{{refend}}

2 : Graph invariants|Graph theory objects
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/23 11:23:31