Decomposizioni in cicli pari di indice 3 nei line graph 4-regolari

An even cycle decomposition (ECD) of an Eulerian graph is a partition of the edge-set into even cycles. We color the even cycles so as two cycles sharing at least one vertex receive distinct colors. If m is the minimum number of required colors, then we say that the even cycle decomposition has index m. The notion of an ECD of index m is connected to the palette index of a graph, a chromatic parameter describing a graph by the minimum number of palettes of its vertices. In particular, the possible values for the palette index of a 4-regular graph are 1, 3, 4 and 5. It is 3 if and only if the graph has an even 2-factor or an ECD of index 3. There exist infinite families of 4-regular graphs with an ECD of index 3 . As far as we know, no example of 4-regular graph whose edge set can be partitioned into even cycles and every ECDs has index larger than 3 is known. Motivated by the problem on the existence of such a 4-regular graph, we study ECDs in 4-regular line graphs of class 2 cubic graphs. For some of the infinite families of class 2 cubic graphs that are characterized by an arbitrary large oddness, we can find an ECD of index 3 in the corresponding line graph.

Una decomposizione in cicli pari (ECD) di un grafo euleriano è una partizione dell'insieme degli spigoli in cicli pari. Coloriamo i cicli pari in modo che i cicli che condividono almeno un vertice ricevano colori distinti. Se m è il numero minimo di colori richiesti, allora diciamo che la decomposizione in cicli pari ha indice m. La nozione di ECD di indice m è connessa al palette index di un grafo, un parametro cromatico che descrive un grafo a partire dal numero minimo di palette dei suoi vertici. In particolare, i possibili valori per il palette index di un grafo 4-regolare sono 1, 3, 4 e 5. Il palette index è 3 se e solo se il grafico ha un 2-fattore pari o un ECD di indice 3. Esistono infinite famiglie di grafi 4-regolari con un ECD di indice 3 . Per quanto ne sappiamo, non è noto alcun esempio di grafo 4-regolare il cui insieme di spigoli può essere partizionato in cicli pari e ogni ECD ha indice maggiore di 3. Motivati dal problema sull'esistenza di un tale grafo 4-regolare, studiamo ECD in line graph 4-regolari di grafi cubici di classe 2. Per alcune delle infinite famiglie di grafi cubici di classe 2, caratterizzati da una grande oddness, possiamo trovare un ECD di indice 3 nel line graph corrispondente.