bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 4 years, 5 months |
seen | Aug 11 at 20:54 | |
stats | profile views | 1,192 |
I am interested in graph theory and combinatorial optimization.
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 |