zbMATH — the first resource for mathematics

Acyclic chromatic index of a subdivided graph. (English) Zbl 0554.05027
An analytic chromatic index a(G) of a graph G is the least number of colours of a regular edge colouring of G in which any adjacent edges have different colours and no cycle is 2-coloured. It was shown by the author [Math. Slovaca 28, 139-145 (1978; Zbl 0388.05015)] that a(G) is finite for every integer h(G), where h(G) is the maximal vertex degree of G. A graph G with \(h(G)=3\) is said to be of class one or two if \(a(G)=3\) or \(a(G)=4\), respectively. In this paper it is proved that: (i) Every cubic graph different from the graphs \(K_ 4\) and \(K_{3,3}\) is of class two; if in the cubic graph (ii) at most two arbitrary edges are subdivided is obtained a graph of class two; (iii) with at most two exceptions every edge is subdivided is produced a graph of class one.
Reviewer: I.Tomescu

05C15 Coloring of graphs and hypergraphs
Zbl 0388.05015
Full Text: EuDML