Interpreting R coxph() cox.zph() The results of my coxph() are significant, yet the cox.zph() test is significant too.
From my understanding of it, the significance of cox.zph() means that the Cox model is not fit to model the relationship between my covariates and the dependent variable. The reason being that this relationship is not linear, while the Cox model only accounts for linear relationships.
I want to know whether there is a relationship between my covariates and survival.
Do the results of the cox.zph() test invalidate the results of the coxph()? 
 A: zph() checks for proportionality assumption, by using the Schoenfeld residuals against the transformed time. Having very small p values indicates that there are time dependent coefficients which you need to take care of. That is to say, the proportionality assumption does not check linearity - the Cox PH model is semi parametric and thus makes no assumption as to the form of the hazard. The proportionality assumption is that the hazard rate of an individual is relatively constant in time, and this is what cox.zph() tests.
If a covariate breaks the assumption, it might need fixing as there are time dependent coefficients. To solve this you can either interact the coefficient with explicit time, or use strata based on the plotted residuals.
For a detailed guide on doing this, see my answer here: Extended Cox model and cox.zph
Without doing something about it, it might invalidate the results, in a similar manner to how breaking linear regression assumptions might.
Edit: 

the effect of holding a diploma on the length of job search vs no diploma. Same scenario : coxph() and zph() significant. Can I say that holding a diploma has an effect on the length of job search?

In all likelihood yes, you could say that. However, given the failed proportionality assumption test, you cannot trust the coefficient of having a diploma (lets call this $diploma$). The Cox model assumes that the effect $diploma$ has on the time to find a job (lets call this $t_{job}$) is constant in time. That means that If $diploma$ increases the % of finding a job by 35%, this increase is irregardless of time. 
In the case that $diploma$ failed the proportionality assumption, as when the cox.zph() test for it is significant, adjustments need to be had. If $diploma$'s coefficient changes linearly with time (i.e., the more time it takes to find a job, the relative benefit of having a diploma linearly declines), than you need to add an interaction: $diploma \times t_{job}$. In this case, the value of $diploma$ will be the initial (at $t_0$ difference between having a diploma and not having a diploma), and the interaction would mean the decrease/increase in that initial value with every passing unit of time (hours/days etc.. however you count time). Do this and check cox.zph() again. If it it non-significant, you can probably leave it at that. It makes more theoretical sense that having the coefficient change at specific time points.
