Search

Um grafo G = (V, E) é bem-coberto se cada conjunto independente maximal de G é máximo. Um grafo G = (V, E) é split se existe uma partição V = (S, K), onde S é um conjunto independente e K é uma clique. Um grafo split bem-coberto é, ao mesmo tempo, split e bem-coberto. Dada uma classe C de grafos, um grafo G = (V, E) é C probe se existe uma partição para V = (N, P ) em probes P e não-probes N , onde N é um conjunto independente e novas arestas podem ser adicionadas entre não-probes de maneira que o grafo resultante permaneça na classe de grafos C. Dizemos que (N, P ) é uma C probe partição para G. O problema C PROBE PARTICIONADO consiste de um grafo de entrada G e uma partição probe V = (N, P ) e a questão: (N, P ) é uma C partição probe? Neste artigo, consideramos C como a classe dos grafos split bem-cobertos, e provamos que o problema C PROBE PARTICIONADO pertence à classe de problemas polinomiais P.

Um grafo é Half Cut se admite um corte de arestas de cardinalidade d m2 e. É sabido que grafos graciosos são Half Cut e os grafos bipartidos completos são graciosos. Neste artigo damos uma prova alternativa de que os grafos bipartidos completos são Half Cut, exibindo um corte de arestas de cardinalidade d m2 e.

Dado um grafo G, sejam vc(G) e vc+(G) os tamanhos de uma cobertura mínima de vértices e de uma máxima cobertura minimal de vértices, respectivamente. Dizemos que G é bem coberto se vc(G) = vc+(G) (ou seja, todas as coberturas minimais são mínimas). É coNP-completo decidir se um grafo é bem coberto. Nesse artigo, obtemos algoritmos FPT de tempos O⇤ (2vc) e O⇤ (1.4656vc+) para decidir se um grafo é bem coberto, parametrizados por vc(G) e vc+(G), respectivamente, melhorando resultados de Boria et al. em 2015. Também obtemos algoritmo FPT parametrizado por ↵ (G) = n vc(G) em grafos d-degenerados, que inclui grafos com genus limitado (como grafos planares) e grafos com grau máximo limitado. Finalmente usamos a decomposição primeval para obter algoritmo linear para grafos P4-laden estendidos e grafos (q, q 4), que é FPT parametrizado por q, melhorando resultados de Klein et al. em 2013.

In this work we present some results on the classical and parameterized complexity of finding cuts in edge-colored graphs. In general, we are interested in problems of finding cuts {A,B} which minimize or maximize the number of colors occurring in the edges with exactly one endpoint in A.

Grafos (3, 6)-fullerenes são grafos planares, 3-conexos, cúbicos cujas faces têm tamanho 3 ou 6. Determinar o menor número de arestas a serem deletadas de um grafo de modo a obter um subgrafo gerador bipartido é conhecido na literatura [Doslic and Vukicevic 2007] como o Problema de Frustração de Arestas. Neste trabalho, abordamos o Problemas da Frustração de Arestas em grafos (3, 6)- fullerenes. Mostramos que todo grafo (3, 6)-fullerene com n vértices torna-se bipartido após a retirada de no máximo q4 3n arestas.