On 2024-07-30 14:13, hermann@stamm-wilbrandt.de wrote:
On 2024-07-28 23:51, hermann@stamm-wilbrandt.de wrote: --%<-- 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.
I made progress, new testcase creates a planar graph verifying that sequential_vertex_coloring() has to use 15 colors (planar graphs can always be vertex colored with 4 colors): https://github.com/Hermann-SW/graph/blob/develop/test/planar_vertex_coloring... A needed operation for planar_vertex_six_coloring() to work is O(1) remove_edge(). I was successful in implementing that, with a single (later protected) new function in undirected_graph.h: https://github.com/Hermann-SW/graph/commit/f7cff30d7d592c7b91d4cd33ea304b9b4... I will have to use "void remove_edge(std::pair< void*, void* > p)" until I find a solution for working recursive type definitions of undirected_graph with edge property and out_edge_iterator. Plan is use derived class undirected_graph_constant_time_edge_add_and_remove which does the needed additional stuff for add_edge() and remove_edge(). A non-class working example is here: https://github.com/Hermann-SW/graph/blob/develop/example/undirected_graph_co... $ f=undirected_graph_constant_time_edge_add_and_remove $ g++ -Wall -Wextra -pedantic $f.cpp -o $f $ $ f=undirected_graph_constant_time_edge_add_and_remove $ cpplint --filter=-runtime/references,-whitespace/braces $f.cpp Done processing undirected_graph_constant_time_edge_add_and_remove.cpp $ g++ -Wall -Wextra -pedantic $f.cpp -o $f $ ./$f 0 <--> 1 2 3 1 <--> 2 0 3 2 <--> 1 0 3 3 <--> 0 1 2 6 edges 0 <--> 3 1 <--> 3 2 <--> 3 <--> 0 1 2 edges 0--3 1--3 $ Regards, Hermann Stamm-Wilbrandt.