Timeline for Bounds on strong vertex colourings of regular hypergraphs?
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Sep 23, 2010 at 10:10 | answer | added | Dave Pritchard | timeline score: 4 | |
| Sep 20, 2010 at 6:43 | comment | added | Niel de Beaudrap | @Andrew: indeed, that construction had occurred to me. In addition to it being lousy, I assumed that anything that any bound that could be achieved by such a simple graph construction was likely to have been surpassed by more sophisticated combinatorial arguments. :-) | |
| Sep 19, 2010 at 16:00 | comment | added | Andrew D. King | As you probably realize, this is equivalent to colouring the graph that you get by replacing the hyperedges with cliques. Doing this gives you an upper bound of $k(\omega-1)+1$ if the hypergraph has maximum edge size $\omega$, by Brooks' Theorem. That's a pretty lousy bound, though, and I imagine you can do better. | |
| Sep 19, 2010 at 12:39 | comment | added | Niel de Beaudrap | @Joseph: thanks, this may prove helpful in the future. I'll take a look at it, but I am interested also in principle in 'non-typical' instances. | |
| Sep 19, 2010 at 12:36 | history | edited | Niel de Beaudrap | CC BY-SA 2.5 |
Completely rephrased in what are hopefully equivalent terms
|
| Sep 15, 2010 at 19:50 | history | edited | Niel de Beaudrap | CC BY-SA 2.5 |
fixed typo
|
| Sep 15, 2010 at 19:41 | history | edited | Niel de Beaudrap | CC BY-SA 2.5 |
corrected minor error
|
| Sep 15, 2010 at 18:36 | comment | added | Joseph O'Rourke | I don't know if this helps, but the asymptotics of the chromatic number for random uniform hypergraphs is known, in a (long!) paper by Krivelevich and Sudakov. | |
| Sep 15, 2010 at 18:18 | history | asked | Niel de Beaudrap | CC BY-SA 2.5 |