Gráficos planares com 3 cores em ?

Fiquei me perguntando se a tarefa de procurar por três cores planares é de complexidade ou inferior? Parece que seria uma consequência intuitiva baseada nos resultados do separador planar; no entanto, na wikipedia , ele menciona apenas conjuntos independentes, árvores Steiner, ciclos hamiltonianos e TSP. Abaixo, incluo algum raciocínio que acho que quase alcança esse limite.$O\left(c^{\sqrt{n}}\right)$

Com um diagrama de decisão com zero reduzido (ZDD), acredito que você pode obter , e fiquei curioso para saber como poderia fazer melhor. O que eu criei é bastante rudimentar. Nota: por toda parte, o ZDD que descrevo é ternário, mas não acho que isso importe muito. Para o ZDD, dada uma ordenação, , de vértices a cores, o número de nós na etapa será exponencial em relação ao tamanho da fronteira, .$O\left(c^{O(log_2(n)\sqrt{n})}\right)$$L = \{v_1 \dots v_n\}$$i$$F_i = \{v_k | k < i \land v_k~v_j, j \geq i \}$

Para criar seu pedido , você pode criar uma árvore de decomposição de ramificação ideal, , em tempo polinomial, que tenha largura no máximo . Em seguida, selecione uma folha aleatória de para ser sua raiz. Com um BFS, pese cada extremidade pelo número de folhas não conectadas a se você remover de . Em seguida, faça um DFS para finalmente criar , sempre descendo a borda mais longe de , escolhendo aquele com menos peso se houver um empate e escolhendo arbitrariamente se ainda houver um empate. Quando chegamos a uma folha, adicione$L$$b$$\sqrt{n}$$v’$$b$$e$$v’$$e$$b$$L$$v’$$(u,v)$$u$vLLcibviLMixibcixlog2bn/ a se ou não está em . Deixe ser o componente induzida em por os vértices visitado quando adicionado para . Em seguida, é limitado pela largura da ramificação vezes o número de arestas precisa ser removido de para obter o componente . é delimitado aproximadamente pelo dos vértices em , que é linear pois estamos lidando com gráficos planares.$v$$L$$L$$c_i$$b$$v_i$$L$$F_i$$x_i$$b$$c_i$$x$$log_2$$b$$n$

Com isso, você verifica todas as três cores de cada nó para cada uma das fronteiras e está pronto.$n$

Recomendo a leitura das Seções 7 e 14 do excelente livro de Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk e Saurabh .

Em resumo, Gu e Tamaki fornecem um algoritmo de tempo quadrático que encontra uma decomposição de ramificação de um gráfico planar de largura no máximo . Então Robertson e Seymour em (5.1) apresentam uma decomposição de árvore de largura menor que . Então o algoritmo clássico de programação dinâmica (ver, por exemplo, Marx ) resolve -Coloring in time .$3\sqrt{n}$ 9 √$\frac{9\sqrt{n}}{2}$ 33 9 √$3$$3^{\frac{9\sqrt{n}}{2}}\textrm{poly}(n)<141^{\sqrt{n}}$

Por outro lado, sabe-se ( Lichtenstein ) que, sob a hipótese de tempo exponencial (ETH), o problema Planar -SAT é -hard. E uma redução de Planar -SAT para Planar -Coloring implica que, sob ETH, não há algoritmo que resolva o Planar -Coloring no tempo .$3$$2^{\Omega(\sqrt{n})}$$3$$3$$3$$2^{o(\sqrt{n})}$