Geodesic
Bipartite ${(6,3)}_6$-biregular graphs which do not allow interval coloring
Daghestan Electronic Mathematical Reports, no. 1 (2014), pp. 71-78 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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.
Mots-clés : bipartite graph
Keywords: 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},
     year = {2014},
     number = {1},
     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
IS  - 1
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
%N 1
%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, no. 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