Bipartite ${(6,3)}_6$-biregular graphs which do not allow interval coloring

A. M. Magomedov

Daghestan Scientific Centre of Russian Academy of Sciences, Makhachkala

Abstract: The proposed in the article search elimination algorithm reduces the problem of finding of a non-colorable graph to building the tree of 11645 nodes, 2485 of which are last level nodes; nodal graphs of the last level form the desired set $M_0$ of ${(6,3)}_6$-graphs. The program found among them just 62 non-colorable graphs, and for $n\le 5$ it constructed colorings for all graphs from the sets – analogues of $M_0$ for considered $n$. Thus specification of minimal $n$, for which the non-colorable ${(6,3)}_6$-graph exists was obtained.

Keywords: bipartite graph, interval edge coloring, job shop scheduling.

UDC: 519.1

Received: 20.11.2013
Revised: 12.05.2014
Accepted: 13.05.2014

DOI: 10.31029/demr.1.3

Bibliographic databases:

•