bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 4 years, 8 months |
seen | yesterday | |
stats | profile views | 1,229 |
I am interested in graph theory and combinatorial optimization.
Sep 7 |
comment |
Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
Good question; it is known to hold, without the round-up. Reed never published the result in a paper but it's in Graph Colouring and the Probabilistic Method (with Molloy), in the chapter on hard-core distributions (Chapter 23 I think). (It wouldn't let me comment twice in a row, so I deleted the old comment to add: ) A proof of a stronger result, noted by McDiarmid, appears in Section 2.2 of my thesis, which is here: columbia.edu/~ak3074/papers/phdthesis.pdf |
Sep 7 |
awarded | Nice Question |
Sep 6 |
comment |
Covering of a graph via independent sets
In that case I would consider how to ask the question in terms of hypergraphs and ask a question in this context. I'm confident somebody will know a better bound than $\Delta+1$. See, for example, this conjecture: garden.irmacs.sfu.ca/?q=op/a_generalization_of_vizings_theorem |
Sep 6 |
revised |
Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
removed latex from title |
Sep 6 |
awarded | Student |
Sep 6 |
asked | Does every triangle-free graph with maximum degree at most 6 have a 5-colouring? |
Sep 4 |
answered | Covering of a graph via independent sets |
Sep 2 |
answered | What are your favorite instructional counterexamples? |
Sep 2 |
comment |
Lower bounds for chromatic number of a graph
By the way, you mention the Kneser graph. This is one graph class that can be used as a nasty example showing that the chromatic number is not necessarily upper-bounded by any function of the fractional chromatic number, meaning that in the worst case, the fractional chromatic number will give you a really lousy approximation. |
Sep 2 |
answered | Lower bounds for chromatic number of a graph |
Sep 2 |
awarded | Supporter |
Mar 12 |
awarded | Editor |
Mar 12 |
revised |
Chromatic number of graphs of tangent closed balls
grammar |
Mar 12 |
awarded | Autobiographer |
Mar 12 |
awarded | Teacher |
Mar 12 |
answered | Suggest effective heuristic (not precise) graph colouring algorithm |
Mar 12 |
answered | Chromatic number of graphs of tangent closed balls |
Mar 12 |
answered | Why is edge-coloring less interesting than vertex-coloring? |
Mar 12 |
answered | Effect on connectivity when partitioning a graph |