wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

arboricity (726B)


      1 # Arboricity
      2 
      3 A [width_measure] on [undirected_graphs]: the minimum number of [spanning_forests] needed to cover all [edges] of the [graph]
      4 - equivalently, the [minimum] number of [forests] in which the [edges] can be partitioned
      5 
      6 A [planar_graph] has arboricity has arboricity at most 3
      7 
      8 Connection between [arboricity] and [dynamic_data] in [lu2021towards]
      9 
     10 - [chiba1985arboricity]
     11 - [danisch2018listing]
     12   - https://papers-gamma.link/paper/32
     13   - https://github.com/maxdan94/kmotif
     14 - [ortmann2014triangle] algorithm for [triangle_listing]
     15 
     16 [bressan2022complexity]: optimality of the results of [chiba1985arboricity] for [graph_pattern_counting]
     17 
     18 Up: [width_measure]
     19 
     20 See also: [degeneracy], [thickness], [pseudoarboricity]