6
$\begingroup$

A linear hypergraph is a hypergraph $H=(V,E)$ such that

  1. $|e|\geq 2$ for all $e\in E$,
  2. $|e_1\cap e_2|\leq 1$ for all $e_1, e_2\in E$ with $e_1\neq e_2$.

An edge coloring of $H$ is a function $c:E\to \{1,\ldots,n\}$ for some integer $n\in\mathbb{N}$ such that whenever $e_1\neq e_2 \in E$ with $e_1\cap e_2 \neq \emptyset$ then $c(e_1)\neq c(e_2)$. The edge coloring number of $H=(V,E)$ is the smallest positive integer $n$ such that there is an edge coloring $c:E\to \{1,\ldots,n\}$.

We call $H=(V,E)$ a near-pencil if there is $v_0$ in $V$ such that $$ E = \big\{\{v_0, v\}: v\in V\setminus \{v_0\}\big\}\cup \big\{V\setminus \{v_0\}\big\}.$$ It is easy to check that any near-pencil is a linear hypergraph.

Question. If $H=(V,E)$ is a linear hypergraph such that $|V| = 2n$ for some positive $n\in\mathbb{N}$ and edge coloring number $|V|$, does this imply that $H$ is a near-pencil?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ The following is obvious but maybe helpful to some: the answer is vacuously yes assuming that $H$ is a graph. Therefore, you could without loss of generality add the hypothesis that $H$ have at least one edge with more than two elements. $\endgroup$
    – Peter Heinig
    Commented May 4, 2017 at 18:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .