pipette
ENEnglish

Melnikov's Valency Variety Problem

Zhanping Yang, Qinghou Zeng

Preprint

En palabras de los autores

Let denote the number of distinct vertex degrees of a finite simple graph . Melnikov asked for a lower bound on the chromatic number in terms of and , and conjectured a strict bound of this type. We resolve Melnikov's valency-variety problem by proving that every graph with at least two vertices satisfies \begin{equation*} \chi(G)\ge\left\lceil1+\frac{2w(G)(w(G)-1)}{4w(G)(|V(G)|-w(G))+(|V(G)|-w(G)-1)^2}\right\rceil, \end{equation*} and consequently \begin{equation*} \chi(G)\ge\left\lceil\frac{\lfloor w(G)/2\rfloor}{|V(G)|-w(G)}\right\rceil. \end{equation*} Finally, we also construct an explicit infinite family of graphs attaining equality in both bounds. In particular, these examples show that Melnikov's proposed strict inequality is false and that the bounds above are best possible.

Resultado principalEl resumen no menciona limitaciones.

Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.