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.