Skip to main content
4 of 6
deleted 12 characters in body
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. Suppose $H=(V,E)$ is a hypergraph. Call a hyperedge $e=\{v_1,v_2,\dotsc,v_k\}$ a $k$-star if in the 1-skeleton of $H$ there is a copy of $K^{1,k-1}$ whose union equals $e$. (Obviously in the case $k=2$, $e$ is an usual edge.)

EDITED: Consider the following three properties:

(a) For every hyperedge $e$ of $H$ there exists $k\in\mathbb{N}$ such that $e$ is $k$-star.

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

(c) between any two hyperedges $e_i$ and $e_j$ we have

$$\text{internal node $\not\in e_i\cap e_j$} $$

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

Let $\Delta(H)$ denote the maximum of vertex-degrees of a finite hypergraph $H$.

Guess. Let $H$ be a simple hypergraph satisfying (a), (b) and (c). Then there exists an $(\Delta+1)$-edge-coloring so that any two edges which share one vertices have distinct colors.

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