1
$\begingroup$

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 two 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.

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) and (c). Then there exists an $(\Delta+1)$-edge-coloring so that any two edges which share one vertices have distinct colors.

Improve this question
$\endgroup$
5
  • $\begingroup$ Dear @C.F.G.: I did a more-or-less complete re-write of your question, because I found it unclear in places. Needless to say, you can re-edit. I don't understand condition (c), and I didn't touch it. Would you please clarify what (c) means? $\endgroup$
    – Peter Heinig
    Commented Apr 5, 2018 at 7:30
  • $\begingroup$ Dear @PeterHeinig, you know that each hyperedge in this question has one central node ( internal node). the means of condition (c) is that internal nodes of hyperedges are not connected to any leaves of hyperedges and not connected to another internal nodes. $\endgroup$
    – C.F.G
    Commented Apr 5, 2018 at 7:51
  • $\begingroup$ thanks for clarifying; however, it is still not clear: the way you defined '$k$-star' and condition (a), the 'internal node' of a hyperedge need not be unique, so (c) is simply undefined. Would you please think about what you are asking and then formulate the question unambiguously? $\endgroup$
    – Peter Heinig
    Commented Apr 5, 2018 at 11:32
  • $\begingroup$ I have deleted the condition (c) but this is not my wanted. I want an extra condition that says: no central node of a hyperedge coincide with leave node of another hyperedge. $\endgroup$
    – C.F.G
    Commented Apr 6, 2018 at 7:21
  • 1
    $\begingroup$ .: re "I want an extra condition that says: no central node of a hyperedge coincide with leave node of another hyperedge.": this is good to know; I was about to point out that your conditions so far seem to make coloring more difficult, and in particular, for any hypergraph $H$ once can easily 'saturate' $H$ with enough 2-element hyperedges to make (a) and (b) while not lowering the chromatic number. The condition you now mentioned makes more sense, since it seems to edge-coloring easier. By the way, do you allow multiple edges' in your 'hypergraphs"? (some peapole do, some don't.) $\endgroup$
    – Peter Heinig
    Commented Apr 6, 2018 at 7:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .