A proper edge coloring of a class 2 graph G is minimal if it contains a color class of cardinality equal to the resistance r(G) of G, which is the minimum number of edges that have to be removed from G to obtain a graph which is Δ(G)-edge colorable, where Δ(G) is the maximum degree of G. In this paper using some properties of minimal edge colorings of a class 2 graph and the notion of reflective edge colorings of the direct product of two graphs, we are able to prove that the double graph of a class 2 graph is of class 1. This result, recently conjectured, is moreover extended to some generalized double graphs.
Minimal edge colorings of class 2 graphs and double graphs
FERRARI, MARGHERITA MARIA;ZAGAGLIA, NORMA
2016-01-01
Abstract
A proper edge coloring of a class 2 graph G is minimal if it contains a color class of cardinality equal to the resistance r(G) of G, which is the minimum number of edges that have to be removed from G to obtain a graph which is Δ(G)-edge colorable, where Δ(G) is the maximum degree of G. In this paper using some properties of minimal edge colorings of a class 2 graph and the notion of reflective edge colorings of the direct product of two graphs, we are able to prove that the double graph of a class 2 graph is of class 1. This result, recently conjectured, is moreover extended to some generalized double graphs.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
1244-4712-1-PB.pdf
accesso aperto
Descrizione: Articolo principale
:
Publisher’s version
Dimensione
154.94 kB
Formato
Adobe PDF
|
154.94 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.