Geodesic
Bipartite ${(6,3)}_6$-biregular graphs which do not allow interval coloring
Daghestan Electronic Mathematical Reports, Tome 1 (2014), pp. 71-78.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DEMR_2014_1_a2,
     author = {A. M. Magomedov},
     title = {Bipartite ${(6,3)}_6$-biregular graphs which do not allow interval coloring},
     journal = {Daghestan Electronic Mathematical Reports},
     pages = {71--78},
     publisher = {mathdoc},
     volume = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DEMR_2014_1_a2/}
}
TY  - JOUR
AU  - A. M. Magomedov
TI  - Bipartite ${(6,3)}_6$-biregular graphs which do not allow interval coloring
JO  - Daghestan Electronic Mathematical Reports
PY  - 2014
SP  - 71
EP  - 78
VL  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DEMR_2014_1_a2/
LA  - ru
ID  - DEMR_2014_1_a2
ER  - 
%0 Journal Article
%A A. M. Magomedov
%T Bipartite ${(6,3)}_6$-biregular graphs which do not allow interval coloring
%J Daghestan Electronic Mathematical Reports
%D 2014
%P 71-78
%V 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DEMR_2014_1_a2/
%G ru
%F DEMR_2014_1_a2
A. M. Magomedov. Bipartite ${(6,3)}_6$-biregular graphs which do not allow interval coloring. Daghestan Electronic Mathematical Reports, Tome 1 (2014), pp. 71-78. http://geodesic.mathdoc.fr/item/DEMR_2014_1_a2/

[1] Svami M., Tkhulasiraman K., Grafy, seti i algoritmy, Mir, M., 1984, 455 pp.

[2] Casselgren C.J., On Some Graph Coloring Problems, Doctoral Thesis, No. 48, Department of Mathematics and Mathematical Statistics Umea University, 2011

[3] Magomedov A.M., K voprosu ob usloviyakh uplotnimosti matritsy iz 6 stolbtsov, Dep. v VINITI, 1991

[4] Karp R.M., “Reducibility among combinatorial problems”, Complexity of Computer Computations, eds. R.E. Miller, J.W. Thatcher, Plenum Press, New York, 1972, 85–103. | DOI | MR