1
$\begingroup$

I have some problem to understand a paper, this paper about "Coloring 2-Intersecting Hypergraphs. A hypergraph is 2-intersecting if any two edges intersect in at least two vertices.

In page 2 Theorem 2 :

Every 2-interseting hypergraph G has a 3-strong coloring with at most five colors.

Proof of Theorem 2 :

We may suppose that $G$ contains three edges with empty intersection, select them with the smallest possible union, let these edges be $e_1, e_2, e_3$ and set $X=e_1 \cup e_2 \cup e_3$. A vertex $v \in X$ is called a private part of $e_i$ if $v \in e_i$ is not covered by any of the other two $e_j-s$

We color the vertices in $X$ as follows. The private parts of $e_1, e_2, e_3$ (if they exist) are colored with $1, 2, 3$ respectively. Notice that each intersection has at least two vertices, color $e_1 ∩ e_3$ with colors $1,3$ so that color $1$ is used only once, color $e_1∩e_2$ with colors $2, 4$ so that color $2$ is used only once. Vertices in $e_2 ∩ e_3$ are all colored with color $5$.

Question : what is the reason they coloring $e_1∩e_3$ with colors $1, 3$ , color $e_1∩e_2$ with colors $2, 4$ and $e_2∩e_3$ are all colored with color $5$ ?

$\endgroup$
1
$\begingroup$

The authors want a 3-strong coloring. In every edge, they need to use at least 3 colors. This is what they achieve by the particular coloring you quoted.

$\endgroup$
  • 1
    $\begingroup$ what would be happend if we change the hypergraph become 3-intersecting ? $\endgroup$ – J. Klins May 1 '17 at 5:30

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.