Applied graph theory

On interval edge $\Delta$-colouring

A. M. Magomedov

Daghestan State University, Makhachkala

Abstract: It is shown that there is a $(6,3)$-biregular graph $G=(X,Y,E)$, such that $|X|+|Y|=33$, with no interval $6$-colourings, and it is proved that the $\Delta$-colouring problem for bipartite multigraph $G=(X,Y,E)$ is $NP$-complete even if $|X|=2$.

UDC: 519.17