If $X$ is any set, we let $[X]^2:=\big\{\{x,y\}:x\neq y\in X\big\}$. If $G=(V,E)$ is an undirected graph and $v\in V$, we define $N\_G(v) = \{w\in V:\{v,w\}\in E\}$.


For $i =1,2$, let $G\_i=(V\_i,E\_i)$ be non-empty, finite, simple, undirected graphs with $V\_1\cap V\_2 = \emptyset$. Suppose that $E \subseteq [V\_1\cup V\_2]^2$ has $E\cap [V\_i]^2=E\_i$ for $i=1,2$, and in addition has the following property:



> 
> there is $k\in\mathbb{N}$ such that $|N\_G(v\_1) \cap V\_2| = k$ for all $v\_1\in V\_1,$
> 
> 
> 


where $G := (V\_1\cup V\_2, E)$.


Is there a "global constant" $c\_k\in\mathbb{N}$ depending on $k$ only such that we have $$\chi(G) \leq \max\{\chi(G\_1), \chi(G\_2)\} + c\_k,$$ no matter what the initial choice of $G\_1, G\_2$ and $E$ (adhering to the property above) was?



"Combined" chromatic number of $2$ graphs glued together with $2$ edges per vertex
This is not true even for $k=1$. Assume that $(V\_1,E\_1)$ is a complete $d$-partite graph with each part having $d$ vertices, and so is $(V\_2,E\_2)$. Take a bijection $f\colon V\_1\to V\_2$ and add edges between $v$ and $f(v)$ for all $d^2$ vertices $v\in V\_1$. $f$ is chosen so that for each part in $V\_1$, its vertices are joined with different parts in $V\_2$ (for example, we may join $i$-th vertex of the $j$-th part in $V\_1$ with $j$-th vertex of $i$-th part in $V\_2$).


Assume that this graph has a proper coloring with $d+c$ colors (where $c=c\_1$ is a constant). Note that each color may be used for the vertices of at most one part in $V\_1$, and analogously for $V\_2$. Therefore at least $d-c$ parts in $G\_1$ are monochromatic, and so are at least $d-c$ parts in $G\_2$. Thus, if $d>3c$, there exists a color (say, white) such that there is a white part in $V\_1$ and white part in $V\_2$. But then there is an edge with white endpoints.


