Geodesic
Interval on one party regular edge 5-coloring of bipatite graph
Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 85-91.

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

For a bipartite graph $G=(X,Y,E)$ where the degree of any vertex in $X$ equals 2 and maximal degree of the vertex in $Y$ equals 5, conditions for existence of regular edge 5-coloring being an interval on $X$
Mots-clés : bipatite graph
Keywords: edge-coloring, NP-completeness. 
@article{PDM_2011_3_a6,
     author = {A. M. Magomedov and T. A. Magomedov},
     title = {Interval on one party regular edge 5-coloring of bipatite graph},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {85--91},
     publisher = {mathdoc},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_3_a6/}
}
TY  - JOUR
AU  - A. M. Magomedov
AU  - T. A. Magomedov
TI  - Interval on one party regular edge 5-coloring of bipatite graph
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 85
EP  - 91
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_3_a6/
LA  - ru
ID  - PDM_2011_3_a6
ER  - 
%0 Journal Article
%A A. M. Magomedov
%A T. A. Magomedov
%T Interval on one party regular edge 5-coloring of bipatite graph
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 85-91
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_3_a6/
%G ru
%F PDM_2011_3_a6
A. M. Magomedov; T. A. Magomedov. Interval on one party regular edge 5-coloring of bipatite graph. Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 85-91. http://geodesic.mathdoc.fr/item/PDM_2011_3_a6/

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

[2] Vizing V. G., “Ob otsenke khromaticheskogo klassa $p$-grafa”, Diskretnyi analiz, 3, Institut matematiki SO AN SSSR, Novosibirsk, 1964, 25–30 | MR

[3] Tait P. G., “Remarks on the previous communication”, Proc. Roy. Soc. Edin., 10 (1880), 729

[4] Tait P. G., “Note on a theorem in the geometry of position”, Trans. Roy. Soc. Edin., 29 (1880), 657–660

[5] Holyer J., “The NP-completeness of edge-colorung”, SIAM J. Comput., 10:4 (1981), 718–720 | DOI | MR | Zbl

[6] Garey M. R., Johnson D. S., Computers and Intractability, W. H. Freeman and Company, San Francisco, 1979 | MR | Zbl

[7] Lovas L., Plammer M., Prikladnye zadachi teorii grafov. Teoriya parosochetanii v matematike, fizike, khimii, per. s angl., Mir, M., 1998

[8] Asratyan A. S., Kamalyan R. R., “Intervalnye raskraski rëber multigrafa”, Prikladnaya matematika, 5, Izd-vo Erevan. un-ta, Erevan, 1987, 25–34 | MR

[9] Magomedov A. M., “Nepreryvnoe raspisanie dlya spetsializirovannykh protsessorov bez otnosheniya predshestvovaniya”, Vestnik Moskovskogo energeticheskogo instituta, 2009, no. 5, 14–17

[10] Giaro K., “The complexity of consecutive $\Delta$-coloring of bipartite graphs: 4 is easy, 5 is hard”, Ars Combin., 47 (1997), 287–298 | MR | Zbl

[11] Hansen H. M., Scheduling with minimum waiting periods, Master Thesis, Odense University, Odense, Denmark, 1992 (in Danish)

[12] Magomedov A. M., Rashaida A., “Matritsa raspisaniya s dvumya nenulevymi elementami v stroke”, Vestnik Dagestanskogo gosuniversiteta, 1999, no. 4, 12–15

[13] Hanson D., Loten C. O. M., Toft B., “On interval colourings of bi-regular bipartite graphs”, Ars Combinat., 4 (1998), 23–32 | MR

[14] Pyatkin A. V., “Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs”, J. Graph Theory, 47:2 (2004), 122–128 | DOI | MR | Zbl

[15] Jensen T. R., Toft B., Graph coloring problems, Wiley-Interscience series in discrete mathematics and optimization, Wiley, New York, 1995 | MR

[16] Asratian A. S., Casselgren C. J., Some results on interval edge colorings of $(\alpha,\beta)$-biregular bipartite graphs, S-581 83, Department of Mathematics, Linköping University, Linköping, Sweden, 2007 | MR

[17] Goldberg A. V., Finding a maximum density subgraph, Technical Report UCB/CSD 84/171, University of California, Berkeley, CA, 1984

[18] Magomedov A. M., “Dva chastichnykh parosochetaniya v dvudolnom grafe spetsialnogo vida”, Materialy X Mezhdunar. seminara “Diskretnaya matematika i ee prilozheniya” (Moskva, MGU, 1–6 fevralya 2010 g.), ed. O. M. Kasim-Zade, Izd-vo mekhmata MGU, M., 2010, 312–313

[19] Magomedov A. M., “Ob odnoi spetsialnoi rëbernoi 2-raskraske”, Razdel “Matematicheskoe modelirovanie: metody, algoritmy, tekhnologii”, Nauchno-tekhnicheskie vedomosti SPbGPU. Cer. Informatika. Telekommunikatsii. Upravlenie, 2011, no. 2(120), 156–159