wiki_research

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

degeneracy (673B)

      1 # Degeneracy
      2 
      3 https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
      4 
      5 An [undirected_graph] is k-degenerate if every [subgraph] has at least one [vertex] of [degree] at most k
      6 - it does not make a difference whether we define this via [subgraphs] or via [induced_subgraphs], cf https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)#Examples
      7 
      8 Special case: [2_degenerate_graphs]
      9 
     10 Some [enumeration] and [counting] problems on graphs have been studied based on degeneracy and arboricity, see [danisch2018listing] for example
     11 
     12 Generalization to [relational_databases]: [partition_constraints] introduced in [deeds2025partition]
     13 
     14 Up: [width_measure]
     15 
     16 See also: [arboricity]