# "Combined" chromatic number of $2$ graphs glued together with $2$ edges per vertex

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?

• Thanks @bof - I will make the notification clearer, and you are right: $2$ is not some "magic" constant: I can do "0 edges connecting $G_1, G_2$", and possibly $1$ edge, but not more. Will generalize to $k$ edges Commented Nov 29, 2022 at 12:12
• Thanks @bof, will modify accordingly Commented Nov 30, 2022 at 9:03

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.