A conjecture on hereditary classes of cubic graphs

Problem's Description

We consider finite, undirected graphs that may contain parallel edges but no loops. If $G$ and $H$ are two cubic graphs, then an $H$-coloring of $G$ is a coloring of edges of $G$ with edges of $H$, such that any three edges incident to a vertex of $G$ are colored by a similar triple of edges of $H$. If $G$ admits an $H$-coloring, then we will write $H\prec G$. If $C$ is a set of connected cubic graphs, then we say that $C$ is hereditary, if for any $G$, $H$, we have $H\prec G$, $H\in C$ implies $G\in C$.

If $H$ is a fixed connected cubic graph, then consider the following decision problem:

$H$-Problem: Given a cubic graph $G$, check whether $G$ admits an $H$-coloring.

Define the class $C_{NPC}$ as follows: $$C_{NPC}=\{H: H-\text{problem is NP-complete}\}.$$

Conjecture: $C_{NPC}$ is a hereditary class of cubic graphs.

1. Article $S_{12}$ and $P_{12}$-colorings of cubic graphs

   • Anush Hakobyan,
   • Vahan Mkrtchyan

   arXiv