Following a given ordering of the edges of a graph G, the greedy edge colouring procedure assigns to each edge the smallest available colour. The minimum number of colours thus involved is the chromatic index χ′(G), and the maximum is the so-called Grundy chromatic index. Here, we are interested in the restricted case where the ordering of the edges builds the graph in a connected fashion. Let χc′(G) be the minimum number of colours involved following such an ordering. We show that it is NP-hard to determine whether χc′(G)>χ′(G). We prove that χ′(G)=χc′(G) if G is bipartite, and that χc′(G)≤4 if G is subcubic.@en

We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a (5 − ε)-approximation, for any ε > 0. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.@en

We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2?(n2) n-vertex graphs as n? ?. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of n/4+o(n) bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of n/4+o(n) bits per vertex and comparability labelling scheme for posets with labels of n/4+o(n) bits per element. All these results are best possible, up to the lower order term. @en