Gráficos cúbicos de partición de bordes en garras y caminos

De nuevo, un problema de partición de bordes cuya complejidad me causa curiosidad, motivado por una pregunta anterior mía .

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

Pregunta: ¿hay una partición de en E 1 , E 2 , ... , E s , de modo que el subgrafo inducido por cada E i sea ​​una garra (es decir, K 1 , 3 , a menudo llamada estrella) o una ruta de 3 ? (es decir, P 4 )?$E$$E_1, E_2, \ldots, E_s$$E_i$$K_{1,3}$$3$$P_4$

Creo que un día vi un artículo en el que se demostró que este problema era NP completo, pero ya no puedo encontrarlo, y no recuerdo si ese resultado se aplicó a los gráficos cúbicos. En un asunto relacionado, soy consciente de que la división de bordes de un gráfico bipartito en garras es NP-complete (ver Dyer y Frieze ). ¿Alguien tiene una referencia para el problema que describo, o algo relacionado (es decir, el mismo problema en otra clase de gráfico, que luego podría intentar reducir a gráficos cúbicos)?

Esta no es una respuesta a la complejidad del problema, pero al menos muestra que la complejidad tiene la posibilidad de no ser trivial: es un ejemplo de un gráfico cúbico que no se puede dividir en caminos y garras.

_{(fuente: uci.edu )}

Dentro de cada uno de sus tres lóbulos, cualquier partición en caminos y garras solo puede usar seis de los siete bordes. Los seis bordes centrales restantes toman la forma de una garra con cada borde subdividido, que no se puede dividir en caminos y garras.

ETA : El gráfico que se muestra arriba es más famoso como un ejemplo de un gráfico cúbico sin una coincidencia perfecta. Pero cada gráfico cúbico con una coincidencia perfecta tiene una descomposición en rutas (ni siquiera usando garras). Según el teorema de König, esto incluye todos los gráficos bipartitos cúbicos y por el teorema de Petersen, esto incluye todos los gráficos cúbicos sin puente, respondiendo una pregunta de Joseph Malkevitch en los comentarios.

La prueba es muy simple: si M es una combinación perfecta en un gráfico cúbico, la eliminación de M deja un gráfico 2-regular, es decir, una unión disjunta de ciclos. Oriente cada ciclo arbitrariamente, y conecte cada borde uv de M a los bordes del ciclo que siguen u y v en las orientaciones de sus ciclos.

En la otra dirección, si existe una descomposición en rutas, entonces existe una coincidencia perfecta: los bordes medios de cada ruta deben coincidir ya que no hay dos bordes medios que puedan compartir un vértice de grado tres.

(Descargo de responsabilidad: esta idea puede haber estado presente en la charla invitada de Carsten Thomassen en GD 2010, que trataba sobre este tipo de problema de descomposición de gráficos).

(además del descargo de responsabilidad (por Anthony Labarre): la "idea de orientación" para pasar de una coincidencia perfecta a una partición en caminos aparece en este documento de Jünger, Reinelt y Pulleyblank , quienes lo atribuyen a WH Cunningham).

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

Este no fue realmente el final de la historia: si el gráfico cúbico es bipartito, entonces es fácil dividir su conjunto de bordes usando solo garras, seleccionando un conjunto de la bipartición y convirtiéndolo en un conjunto de "centros de garras". El problema general es realmente difícil, lo que se puede probar utilizando una reducción de la SATISFIABILIDAD CUBICA PLANAR MONOTONE 1 EN 3. Todos los detalles son de libre acceso en arxiv .

Quizás este documento pueda ser de interés:

Kleinschmidt, Peter Particiones regulares de gráficos regulares. Canad. Matemáticas. Toro. 21 (1978), no. 2, 177-181.

Se trata de gráficos que se pueden escribir como la unión de "Z-caminos" de longitud 3. (Específicamente, planar, 3-valent, 3 conectados-gráficos-cúbicos 3-politopos).