1
$\begingroup$

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$.)

$\endgroup$

1 Answer 1

2
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .