h-index

equivalent to: distance to maximum degree, h-index

Relations

Results

• 2019 The Graph Parameter Hierarchy by Sorge
  • page 8 : h-index upper bounds acyclic chromatic number by a polynomial function – Lemma 4.7. The acyclic chromatic number $\chi_a$ is upper bounded by the $h$-index $h$. We have $\chi_a \le h(h+1)/2$.
• https://link.springer.com/chapter/10.1007/978-3-642-03367-4_25
  • h-index – … $h$ is the $h$-index of the graph, the maximum number such that the graph contains $h$ vertices of degree at least $h$.
• Comparing Graph Parameters by Schröder
  • page 12 : distance to linear forest upper bounds h-index by a linear function – Proposition 3.2
  • page 25 : bounded treedepth does not imply bounded h-index – Proposition 3.22
  • page 25 : bounded feedback edge set does not imply bounded h-index – Proposition 3.22
• 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.
  • h-index upper bounds distance to maximum degree by a linear function – Remove the $h$ vertices of degree at least $h$ to get a graph that has maximum degree $h$.
  • distance to maximum degree upper bounds h-index by a linear function – Removal of $k$ vertices yielding a graph with maximum degree $c$ means that there were $k$ vertices of arbitrary degree and the remaining vertices had degree at most $k+c$. Hence, $h$-index is no more than $k+c$.
  • graph class stars has unbounded h-index
  • graph class star has constant h-index – trivially
  • graph class tree has unbounded h-index – trivially