maximum degree

equivalent to: maximum degree

providers: ISGCI

Relations

Results

• 2022 Expanding the Graph Parameter Hierarchy by Tran
  • page 32 : maximum degree upper bounds c-closure by a linear function – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
  • page 32 : bounded c-closure does not imply bounded maximum degree – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
  • page 40 : bounded twin-width does not imply bounded maximum degree – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
  • page 40 : bounded maximum degree does not imply bounded twin-width – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
• 2019 The Graph Parameter Hierarchy by Sorge
  • page 8 : maximum degree upper bounds acyclic chromatic number by a polynomial function – Lemma 4.6 ([15]). The acyclic chromatic number $\chi_a$ is uppre bounded by the maximum degree $\Delta$ (for every graph with $\Delta > 4$). We have $\chi_a \le \Delta(\Delta-1)/2$.
• 2013 Characterizing graphs of small carving-width by Belmonte, van ’t Hof, Kamiński, Paulusma, Thilikos
  • carving-width upper bounds maximum degree by a linear function – Observation 1. Let $G$ be a graph. Then $cw(G) \ge \Delta(G)$.
• 2010 Comparing 17 graph parameters by Sasák
  • page 28 : cutwidth upper bounds maximum degree by a linear function – Lemma 2.18. For any graph $G$ and any vertex $v \in V(G), cutw(g) \ge \lceil \frac{deg(v)}2 \rceil$.
  • page 30 : carving-width upper bounds maximum degree by a linear function – Lemma 2.20 Carving-width of a graph $G$ is at least $\Delta(G)$ where $\Delta(G)$ is the maximum degree of a graph $G$.
• assumed
  • pathwidth+maxdegree upper bounds maximum degree by a linear function – by definition
  • degree treewidth upper bounds maximum degree by a linear function – by definition
  • maximum degree upper bounds distance to maximum degree by a linear function – by definition
  • graph class grid has constant maximum degree – By definition
  • bounded components upper bounds maximum degree by a linear function – By definition
  • graph class linear forest has constant maximum degree – By definition
  • graph class cycles has constant maximum degree – By definition
  • diameter+max degree upper bounds maximum degree by a linear function – by definition
• Comparing Graph Parameters by Schröder
  • page 24 : bounded vertex cover does not imply bounded maximum degree – Proposition 3.19
  • page 28 : bounded maximum degree does not imply bounded clique-width – Proposition 3.26
  • page 28 : bounded maximum degree does not imply bounded bisection bandwidth – Proposition 3.26
• unknown source
  • maximum degree upper bounds h-index by a linear function – As h-index seeks $k$ vertices of degree $k$ it is trivially upper bound by maximum degree.
  • bandwidth upper bounds maximum degree by a linear function – Each vertex has an integer $i$ and may be connected only to vertices whose difference from $i$ is at most $k$. There are at most $k$ bigger and $k$ smaller such neighbors.
  • maximum degree upper bounds c-closure by a computable function
  • maximum degree – maximum degree of graph’s vertices
  • graph class grid has constant maximum degree
  • graph class planar has unbounded maximum degree
  • graph class star has unbounded maximum degree – trivially