Discrete Math

Daghestan Electronic Mathematical Reports: Issue 1 (2014)

Bipartite (6.3)-biregular graphs which do not allow interval coloring

UDK: 519.1

Pages: 71 - 78

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.

To issue content

Download full text