degeneracy

tags: vertex order

equivalent to: degeneracy, arboricity

providers: ISGCI

Relations

Results

• 2022 Expanding the Graph Parameter Hierarchy by Tran
  • page 42 : bounded degeneracy does not imply bounded boxicity – Proposition 7.1. Degeneracy is incomparable to Boxicity.
  • page 42 : bounded boxicity does not imply bounded degeneracy – Proposition 7.1. Degeneracy is incomparable to Boxicity.
• 2019 The Graph Parameter Hierarchy by Sorge
  • page 8 : arboricity upper bounds degeneracy by a linear function – Lemma 4.5
  • page 8 : degeneracy upper bounds arboricity by a linear function – Lemma 4.5
  • page 9 : acyclic chromatic number upper bounds degeneracy by a polynomial function – Lemma 4.18. The acyclic chromatic number $a$ upper bounds the degeneracy $d$. We have $d \le 2 \binom a2 - 1$
• https://en.wikipedia.org/wiki/Degeneracy_(graph_theory)
  • degeneracy – … the least $k$ for which there exists an ordering of the vertices of $G$ in which each vertex has fewer than $k$ neighbors that are earlier in the ordering.
• unknown source
  • degeneracy upper bounds chromatic number by a linear function – Greedily color the vertices in order of the degeneracy ordering. As each vertex has at most $k$ colored predecesors we use at most $k+1$ colors.
  • degeneracy upper bounds average degree by a linear function – Removing a vertex of degree $d$ increases the value added to the sum of all degrees by at most $2d$, hence, the average is no more than twice the degeneracy.