On 2024-07-28 23:51, hermann@stamm-wilbrandt.de wrote:
... I would start by taking https://www.boost.org/doc/libs/1_85_0/libs/graph/doc/sequential_vertex_color... as a template for "planar_vertex_coloring.hpp".
My plan is to first port my existing fast linear time "six_coloring()" https://github.com/Hermann-SW/planar_graph_playground/blob/main/c%2B%2B/undi... and learn about the review process with it.
I made some investigations regarding Boost sequential_vertex_coloring() use of colors for random maximal planar graphs of various sizes: https://gist.github.com/Hermann-SW/5e74ee13fbf1d0103061e95d8a67c2f7?permalin... For graphs of 100 or 1,000 vertices (always 1,000 graphs tested) some graphs did need 5 colors. But for random maximal planar graphs with 10,000 or 100,000 vertices always 6 colors were used. So next I crafted 7c.u and 8c.u small maximal planar graphs that force sequential_vertex_coloring() to use 7 or even 8 colors. Details in the next comments of the gist pointed to. My six_coloring() uses sequential vertex coloring as well, but with a special order of vertices with the help of 5-compaction of input graph. So instead of completely port my existing code pointed to in last email, I will determine the vertex order and call Boost sequential_vertex_coloring() to determine vertex coloring with maximally 6 colors.
I looked at commits in Boost graph directory and there is not that much recent activity. Is my plan and the steps outlined the right way to start?
Am I good to proceed as planned? Regards, Hermann Stamm-Wilbrandt.