##
On Consecutive Coloring the Edges of a Graph

Marek E. Kubale
Department of Foundations of Informatics

Technical University of Gdansk

ul. Narutowicza 11/12

80-952 Gdansk, Poland

kubale@pg.gda.pl

### ABSTRACT

A proper edge-coloring c of G with natural numbers is consecutive if the
colors of edges incident with each vertex form an interval. The span of c
is the number of colors used in the consecutive coloring and chi_c'(G) stands
for the minimum span among all consecutive colorings of G. If G does not
have such a coloring, then the deficiency d(G) of G is the minimum number
of pendant edges whose attachment to G makes it consecutively colorable.

In the talk we investigate these concepts mostly in the case of bipartite
graphs. Namely, we show that the problem of deciding if a bipartite graph
G is consecutively DELTA-colorable is NP-complete for DELTA >= 5. Then
we review special cases of bipartite graphs that have such a coloring of
edges, e.g. trees, cacti, complete bipartite, (2,DELTA)-regular, grid
graphs and show that for some of them lim_n chi_c'(G)/DELTA = inf. Finally, we
investigate bipartite graphs which are not consecutively colorable and
show that for some of them lim_n d(G)/n = 1.

Colloquia Series page.