1
$\begingroup$

Let $M$ be a set of straight lines. Define an EFL coloring of $M$ with $k$ colors as a function $f : P(M) \rightarrow \{ 1,2,\dots,k \}$, such that if two intersection points $p_1, p_2$ belong to the same line, then $f(p_1) \neq f(p_2)$. ($P(M)$ is the set of all intersection points of lines from $M$.) Denote by $\chi_E(M)$ the minimum number of colors needed for an EFL coloring of $M$. \

Question: Prove that the problem of finding $\chi_E(M)$ is NP-hard.\

Any helpful suggestion/hint would be greatly appreciated.

$\endgroup$
1
  • $\begingroup$ Is your EFL terminology derived from the Erdos-Faber-Lovasz problem? Your problem is just equivalent to that problem I suppose, by putting all interesection points of one single line in a clique. Then, by this breakthrough paper's introductory disussions, and the randomized algoritthm they give, it should be quick to say it is NP-Hard, I suppose $\endgroup$
    – vidyarthi
    Dec 19, 2022 at 17:34

0

Your Answer

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