Digraphs Improve `ChromaticNumber`

Currently, ChromaticNumber does a linear search for the chromatic number. It'd be much better if it did a binary search.

Mar 18 '19 10:03 james-d-mitchell

It is not clear whether this is actually faster. Binary search (happens) typically by repeatedly under- and over-estimating the solution. For chromatic number, it is normally much quicker to determine whether your guess is an overestimate (simply find a colouring with that many colours) than an underestimate (this requires proving that no colouring is proper, which is perhaps very expensive). So perhaps the current method, which I assume starts with an overestimate and decreases that estimate linearly, is the fastest way in general. We could do experiments to determine this.

Mar 18 '19 12:03 wilfwilson

Fair point @wilfwilson, maybe the issues is that we should just improve the ChromaticNumber method so it's faster, perhaps using Leonard Soicher's approach.

Mar 19 '19 09:03 james-d-mitchell

And Leonard feels that, for his approach, the binary search would be appropriate.

Mar 19 '19 13:03 wilfwilson