3
$\begingroup$

For any set $X$, let $[X]^2 = \big\{\{a,b\}:a,b \in X, a\neq b\big\}$.

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

  1. each $S_k$ has $n$ elements for $k\in\{1,\ldots, n\}$,
  2. $|S_k\cap S_j|\leq 1$ for $k\neq j\in \{1,\ldots, n\}$, and
  3. $V = \bigcup_{k=1}^n S_k$, and $E = \bigcup_{k=1}^n [S_k]^2$.

The Erdos-Faber-Lovasz conjecture says that if $G$ is an $n$-EFL-graph, then $\chi(G) \le n$.

Given any finite, simple, undirected graph $G=(V,E)$, the Hadwiger number $\eta(G)$ is the maximum $n\in\mathbb{N}$ such that $K_n$ is a minor of $G$.

Question. Is there $C\in\mathbb{N}$ such that for all $n\in\mathbb{N}$, if $G$ is an $n$-EFL-graph, then $\eta(G) \leq Cn$?

Improve this question
$\endgroup$
2
  • $\begingroup$ I cannot follow your "Note". Hadwiger's conjecture asserts that $\chi(G)\leq \eta(G)$. The section "History and partial results" of the wikipedia article you link to mentions a result of Chang and Lawler according to which $\chi(G)\leq \tfrac{3}{2}\eta(G)-2$. Both results provide lower bounds for $\eta(G)$, but the question asks for an upper bound. $\endgroup$
    – Philipp Lampe
    Commented Sep 5, 2018 at 14:25
  • $\begingroup$ @PhilippLampe You are right, I will remove the note (= last sentence in the post) $\endgroup$
    – Dominic van der Zypen
    Commented Sep 6, 2018 at 6:08

0

Reset to default

You must log in to answer this question.