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?

  • $\begingroup$ 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 $\endgroup$ Commented Nov 29, 2022 at 12:12
  • $\begingroup$ Thanks @bof, will modify accordingly $\endgroup$ Commented Nov 30, 2022 at 9:03

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.