1,145 reputation
814
bio website andrewdouglasking.com
location Vancouver
age 34
visits member for 4 years, 8 months
seen yesterday
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