Estou tentando entender alguns conceitos sobre decomposição modular e gráficos de largura de clique .
Em deste artigo ( "On gráficos P4-arrumado"), não é uma prova de como resolver problemas de otimização como camarilha-número ou cromática-número usando decomposição modular. Resolvendo esses problemas compondo (usando soma ou união disjunta) dois gráficos G1, G2 é fácil quando você conhece a resposta para G1 e G2. Como os gráficos primos na decomposição dos gráficos ordenados P4 são gráficos delimitados (ou seja, C5, P5, etc.), É fácil resolvê-lo para esses "casos de base" e depois para composições. Portanto, usando a árvore de decomposição, é possível resolver esses problemas em tempo linear.
Mas parece que essa técnica funcionaria com qualquer classe de gráfico, de modo que os primos de gráfico sejam limitados. Então, encontrei este artigo "Problemas de otimização resolvível em tempo linear em gráficos de largura de clique limitado", que parece fazer a generalização que eu estava procurando, mas não conseguia entender muito bem.
Minha pergunta é:
1- É equivalente dizer que os gráficos primos da árvore de decomposição são delimitados (como no caso dos gráficos P4-Tidy) e dizer que um gráfico tem a propriedade "Clique-Width" delimitada?
2- Caso a resposta para 1 seja NÃO, existe: Existe algum resultado sobre classes de gráficos com números primos delimitados (como nos gráficos ordenados P4) e, portanto, problemas de otimização como número de clique solucionável no tempo linear em todas essas classes ?
fonte