4
votes
1answer
195 views

2-Coloring a planar hypergraph

Consider a hypergraph (of rank 3) $H = (V, E)$ (where the rank of $H$ is the maximum cardinality of a hyperedge). $H$ is said to be planar if we can construct a planar graph $G = (V, A)$, and a ...
7
votes
0answers
214 views

A maximum discrepancy hypergraph 2-colouring problem

This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now. The setup is as follows. We have a vertex set partitioned in to sets ...
3
votes
3answers
320 views

Can you prove that hypergraphs with n-1 edges are partially 2 colorable?

I can. But my proof uses a theorem (which I do not reveal yet to avoid influencing you) and it feels like an overkill, so I wonder if there is a simple proof. Now the problem. Suppose we have a ...
4
votes
1answer
545 views

Hypergraph Chromatic Number vs Degree, Clique-Size

For a hypergraph let $\chi$ be the least number of colours needed to colour the vertices, so that in each edge, each colour is used at most once (i.e., the strong chromatic number). Let $\Delta$ be ...
4
votes
1answer
398 views

Bounds on strong vertex colourings of regular hypergraphs?

What are the best results for upper bounds on the number of colours required in a strong vertex colouring of a regular hypergraph H? A regular hypergraph is one in which every vertex is contained in ...