Gráficos cúbicos de particionamento de arestas em garras e caminhos

Novamente, um problema de particionamento de borda cuja complexidade me interessa, motivada por uma pergunta anterior minha .

Entrada: um gráfico cúbico$G=(V,E)$

Pergunta: existe uma partição de em , de modo que o subgráfico induzido por cada seja uma garra (ou seja, , freqüentemente chamada de estrela) ou um caminho de ( ie )?E 1 , E 2 , … , E s E i K 1 , 3 3 P $E$$E_1, E_2, \ldots, E_s$$E_i$$K_{1,3}$$3$$P_4$

Acho que vi um artigo um dia em que esse problema foi comprovado como NP-completo, mas não consigo mais encontrá-lo e não me lembro se esse resultado se aplicava a gráficos cúbicos. Em um assunto relacionado, estou ciente de que o particionamento de borda de um gráfico bipartido em garras é NP completo (consulte Dyer e Frieze ). Alguém tem uma referência para o problema que eu descrevo, ou algo relacionado (ou seja, o mesmo problema em outra classe de gráfico, que eu poderia tentar reduzir a gráficos cúbicos)?

Isso não é uma resposta para a complexidade do problema, mas pelo menos mostra que a complexidade tem uma chance de não ser trivial: é um exemplo de um gráfico cúbico que não pode ser particionado em caminhos e garras.

_{(fonte: uci.edu )}

Dentro de cada um de seus três lóbulos, qualquer partição em caminhos e garras pode usar apenas seis das sete arestas. As seis arestas centrais restantes assumem a forma de uma garra com cada aresta subdividida, que não pode ser dividida em caminhos e garras.

ETA : O gráfico mostrado acima é mais famoso como um exemplo de gráfico cúbico sem uma correspondência perfeita. Mas todo gráfico cúbico com uma correspondência perfeita tem uma decomposição em caminhos (nem mesmo usando garras). Pelo teorema de König, isso inclui todos os gráficos bipartidos cúbicos e pelo teorema de Petersen isso inclui todos os gráficos cúbicos sem ponte, respondendo a uma pergunta de Joseph Malkevitch nos comentários.

A prova é muito simples: se M é uma combinação perfeita em um gráfico cúbico, a remoção de M deixa um gráfico 2-regular, ou seja, uma união disjunta de ciclos. Oriente cada ciclo arbitrariamente e conecte cada aresta uv de M às arestas do ciclo que seguem u e v nas orientações de seus ciclos.

Na outra direção, se houver uma decomposição em caminhos, haverá uma correspondência perfeita: as arestas do meio de cada caminho devem ser uma correspondência, pois nenhuma aresta do meio pode compartilhar um vértice de grau três.

(Aviso: esta ideia pode já estar presente na palestra convidada de Carsten Thomassen na GD 2010, que tratava desse tipo de problema de decomposição de gráficos.)

(além do aviso de isenção de responsabilidade (de Anthony Labarre): a "ideia de orientação" para passar de uma combinação perfeita para uma partição em caminhos aparece neste artigo por Jünger, Reinelt e Pulleyblank , que a atribuem a WH Cunningham.)

$k$$k\geq 3$$k=3$$2$$3$

Na verdade, esse não era o fim da história: se o gráfico cúbico é bipartido, é fácil particionar seu conjunto de arestas usando apenas garras, selecionando um conjunto da bipartição e transformando-o em um "centro de garras". O problema geral é realmente difícil, o que pode ser provado usando uma redução da SATISFIABILIDADE 1-EM-3 DO MONOTONE CUBIC PLANAR. Todos os detalhes são acessíveis gratuitamente no arxiv .

Talvez este artigo possa ser interessante:

Kleinschmidt, Peter Partições regulares de gráficos regulares. Canadá. Matemática. Touro. 21 (1978), n. 2, 177-181.

Ele lida com gráficos que podem ser escritos como a união de "caminhos Z" de comprimento 3. (Especificamente, 3-polítopos gráficos cúbicos planares, com 3 valentes e 3 conectados).