h-index

• 2019 Sorge2019
  • page 8 : h-index $k$ upper bounds acyclic chromatic number by $k^{\mathcal O(1)}$ – 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$.
• SchroderThesis
  • page 12 : distance to linear forest $k$ upper bounds h-index by $\mathcal O(k)$ – 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
• 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$.
• unknown
  • maximum degree $k$ upper bounds h-index by $\mathcal O(k)$ – As h-index seeks $k$ vertices of degree $k$ it is trivially upper bound by maximum degree.
  • h-index $k$ upper bounds distance to maximum degree by $\mathcal O(k)$ – Remove the $h$ vertices of degree at least $h$ to get a graph that has maximum degree $h$.
  • distance to maximum degree $k$ upper bounds h-index by $\mathcal O(k)$ – 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