Consider two edge disjoint graphs $G_1$ and $G_2$ having the null graph on $k$ vertices as their intersection, where $k$ is less than or equal to the the total vertices in $G_1$ and $G_2$. Then, would the union (the union of edge and vertex sets) of $G_1$ and $G_2$ have chromatic number at most one more than the maximum of the individual chromatic numbers of $G_1$ and $G_2$?
I feel this is untrue. Any easy counterexamples? Or, is the proposition true? Thanks beforehand.
I assume you mean that $V(G_1)\cap V(G_2)=W$ where $W$ is a set of $k$ vertices which is an independent set in both $G_1$ and $G_2$? In this case it is true.
Start with any colouring of $G_1$ with colours $1,...,\chi(G_1)$, and any colouring of $G_2$ with colours $1,...,\chi(G_2)$. We use these to define the colours on $V(G_1)\cup V(G_2)\setminus W$, and then colour all vertices in $W$ with the new colour $\max(\chi(G_1),\chi(G_2))+1$.
The $+1$ is necessary, e.g. if $G_1$ is an odd path and $G_2$ an even path with common endvertices.