Skip to main content
1 of 6
C.F.G
  • 4.2k
  • 6
  • 31
  • 65

Does anybody know how to prove or disprove the following guess about edge coloring of Hypergraphs?

Definition. Call an hyperedge $e=\{v_1,v_2,...,v_k\}$, $k$-star ($k\geq 3$) if all its vertices form a $k$-star graph. i.e. a tree with one internal node and $k-1$ leaves. Obviously in the case $k=2$, $e$ is an usual edge.

Consider the following two properties:

(a) All hyperedges of $H$ are of the form $k$-star for some $k\in \Bbb N$;

(b) If two hyperedges $e_1$ and $e_2$ which share at least one vertices ($|e_1\cap e_2|\geq1$) then there is an usual edge that connect internal nodes of this two hyperedges.

Question: Does anybody know how to prove or disprove the following guess about edge coloring of Hypergraphs?

Guess. Let $H$ be a simple hypergraph satisfies in (a) and (b). Then there exists an $(\Delta +1)$- edge-coloring so that any two edges which share one vertices have distinct colors where each vertex is of degree at most $\Delta$.

C.F.G
  • 4.2k
  • 6
  • 31
  • 65