Existence of $C$ such that $p(x) \leq p(y) + C$ for all $x \leq y$ Suppose I have a polynomial $p$ of order $n$, which we can assume is positive, i.e. if $p(x) = \sum_{i=0}^n a_ix^i$ then $a_n > 0$. I am interested in the existence or non-existence of a constant $C \geq 0$ such that $p(x) \leq p(y) + C$ for all $0 \leq x^n \leq y^n + K$ and with $x, y \geq 0$.
Here are some thoughts when $K = 0$ and hence $0 \leq x \leq y$. We let $A = \{0 \leq x \leq y\} \subset \mathbb R^2$, and I think I can reformulate by question as whether or not there exists a $C$ such that $f(x, y) = p(y) - p(x) + C \geq 0$ for all $(x, y) \in A$.
I can find a $C$ if the region is compact by continuity, say if $y \leq L$ for any $L$, and for $x \geq L$ where $L$ is sufficiently large, eventually $p(x)$ is increasing so $p(y) - p(x)$ for $y \geq x$. On the region $x \leq L$ and $y \geq L$, and for $L$ sufficiently large again, we have that $p(x)$ is bounded and $p(y)$ is positive so a $C$ exists here as well.
What if $K \neq 0$? In this case I can see the analogous argument with $0 \leq x \leq y + K'$ is not strong enough. (This we can obtain from the fact if $x^n \leq y^n + K$ then $x \leq (y^n + K)^{1/n} \leq y + K^{1/n}$.) For instance if $p(x) = x^2$ and $y = x - K'$ then $y^2 - x^2 = -2xK' + (K')^2$ which can be arbitrarily large and negative by taking $x \rightarrow \infty$. So it seems to me that control over what happens at top order is necessary (thus we need $x^n \leq y^n + K$ and not just $x \leq y + K'$), but I don't know how to put this argument correctly/nicely.
EDIT: Thanks to a comment below, an extra condition $x, y \geq 0$ has been imposed.
 A: One can find an upper bound for $p(x)-p(y)$ as follows:
First consider a decomposition of the polynomial into it's negative and positive coefficients
$$p(x)=p_+(x)+p_-(x)=\sum_{i=1}^{A}P_{i}x^{p_i}+\sum_{i=1}^{n-A}Q_{i}x^{q_i}$$
where $P_i>0, Q_i<0$. Next, one can show that on each curve $x^n-y^n=K$, the function $p(x)-p(y)=p((y^n+K)^{1/n})-p(y)$ is bounded. Consider the function
$$f(y)=(y^n+K)^{m/n}-y^m$$
This function is monotonically decreasing for $y\geq 0$ and also $\lim_{y\to\infty} f(y)=0$ and it is bounded below and above by
$$0<f(y)\leq K^{m/n}$$
We can now write
$$p(x=(y^n+K)^{1/n})-p(y)=\sum_{i=1}^{A}P_{i}(x^{p_i}-y^{p_i})+\sum_{i=1}^{n-A}Q_{i}(x^{q_i}-y^{q_i})<\sum_{i=1}^AP_iK^{p_i/n}=p_+(K^{1/n})$$
and we conclude that in the interval $K\in(0,K_{\max})$, which spans the region $0\leq x^n-y^n\leq K_{max}~,~ x\geq0, y\geq 0$, the quantity of interest is bounded, and since $p_+$ is an increasing function for $K\geq 0$ the universal bound is
$$p(x)-p(y)<C:=p_+(K_{\max}^{1/n})$$
