We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdos graph if there are $n$ subsets $S_1,\ldots, S_n$ of $V$ such that

  1. $V = \bigcup_{n=1}^n S_n$;
  2. each $S_k$ has $n$ elements for $k\in\{1,\ldots, n\}$;
  3. $\{a,b\}\in E$ implies that there is $k\in\{1,\ldots,n\}$ such that $a, b\in S_k$;
  4. $k\neq j\in \{1,\ldots, n\}$ imply $|S_k\cap S_j|\leq 1$.

One version of the Erdos-Faber-Lovasz conjecture says that if $G$ is an $n$-Erdos graph, then $\chi(G) \leq n$.

We say that $G$ is a weak $n$-Erdos graph if items 1.-3. above are satisfied, but not necessarily number 4.

Is there $k\in \mathbb{R}$ with $k>1$ such that for all $n\in \mathbb{N}$ we have that if $G$ is a weak $n$-Erdos graph, then $\chi(G) \leq k\cdot n$? If yes, what is the smallest such $k$?

(Note: for $n=3$ it is possible to find a weak $n$-Erdos graph $G$ with $\chi(G) = 4$, maybe I add the example later on. So if such a $k$ exists we have $k\geq 4/3$.)


A complete graph with $\Theta(n^{3/2})$ vertices can be a weak $n$-Erdos graph.

Let $m$ be the largest integer satisfying $m(m-1)/2 \le n$. Consider $m$ disjoint copies of sets $V_1, \dots, V_m$ each with $\lfloor n/2 \rfloor$ elements. Let the sets $S_i$s be $$\{S_1, S_2, \dots, S_{m(m-1)/2}\} = \{V_1 \cup V_2, V_1 \cup V_3, \dots, V_{m-1} \cup V_m\}.$$ Then the complete graph on the set of vertices $V_1 \cup \dots \cup V_m$ is a weak $n$-Erdos graph with $mn$ vertices. Clearly, the chromatic number of this graph is $mn \sim cn^{3/2}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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