The edge chromatic difference sequence of a cubic graph
Let \(\gamma_r (G)\) be the maximum number of edges in an \(r\)-edge-colourable subgraph of a graph \(G\). The chromatic difference sequence \(\langle c_1,c_2,\dots, c_k\rangle\) is obtained by setting \(c_1= \gamma_1(G)\) and \(c_i= \gamma_i(G)- \gamma_{i-1} (G)\), \(i\geq 2\), where \(k\) is the chromatic index of \(G\). In the paper, the behaviour of chromatic difference sequences of cubic graphs is investigated. It is proved that \(c_1\geq c_2\geq c_4\) and \(c_1\geq c_3\geq c_4\). Examples are exhibited to show that the chromatic difference sequence of a cubic graph can, nevertheless, be non-monotonic.
scientific article; zbMATH DE number 1110103