Colouring series-parallel graphs (Q2640612): Difference between revisions

The graphs under consideration are finite, and may have multiple edges but not loops. A graph is series parallel if it can be reduced to the null graph by repeated use of three operations: (i) delete an edge parallel with another edge, (ii) contract an edge incident with a vertex of valency 2, and not parallel with the second edge at this vertex, (iii) delete a vertex of valency \(\leq 1.\) A first result concerns the chromatic index \(\chi '(G)\) (the minimum number of colours of a proper edge colouring) of a series-parallel graph with maximum valency \(\leq k\), such that \(k\cdot | X| -2| \bar X| \geq k\) for every subset X of odd cardinality \(| X|\) of the vertex set. In this case \(\chi '(G)\leq k\) holds. A second result is the proof of the correctness of a ``greedy algorithm'' for finding a vertex colouring of a series-parallel graph.