Coloring 2-Intersecting Hypergraphs

139 Views Asked by At

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$ ?

1

There are 1 best solutions below

1
On

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.