Mobile 3-uncolorable Vertices Recognizable in Polynomial Time in Planar Graph with Degree no More Than 4
Zhongzhu Liu, Liu Teng, Xiao Chan Wang · 2024
To find more 3-uncolorable vertices recognizable in polynomial time, we consider mobile 3-uncolorable vertices. In color space, the transfer is expressed by shift of dot strings in alternate configurations. An alternate configuration is the union of a DJC and movable dot strings relative to the DJC. It has several FLC one of which is a WFLC. The movement of the movable dot string exchanges FLC with WFLC to ensure that WFLC exists always in the configuration. We prove that an additional dot string (ADS) to an alternate configuration may turn the configuration to be a triplet. So, 3-uncolorable vertices in the graph of alternate configurations in planar graph with degree more than 4 G(V,E) can be recognized in O(|V 8 |). We need to find more recognizable 3-uncolorable vertices in polynomial time for judging 3-coloring of planar graph.