On one-sided interval edge colorings of biregular bipartite graphs

Rafayel Ruben Kamalian

Algebra and discrete mathematics, Tome 19 (2015) no. 2, pp. 193-199.

Résumé

A proper edge $t$-coloring of a graph $G$ is a coloring of edges of $G$ with colors $1,2,\ldots,t$ such that all colors are used, and no two adjacent edges receive the same color. The set of colors of edges incident with a vertex $x$ is called a spectrum of $x$. Any nonempty subset of consecutive integers is called an interval. A proper edge $t$-coloring of a graph $G$ is interval in the vertex $x$ if the spectrum of $x$ is an interval. A proper edge $t$-coloring $\varphi$ of a graph $G$ is interval on a subset $R_0$ of vertices of $G$, if for any $x\in R_0$, $\varphi$ is interval in $x$. A subset $R$ of vertices of $G$ has an $i$-property if there is a proper edge $t$-coloring of $G$ which is interval on $R$. If $G$ is a graph, and a subset $R$ of its vertices has an $i$-property, then the minimum value of $t$ for which there is a proper edge $t$-coloring of $G$ interval on $R$ is denoted by $w_R(G)$. We estimate the value of this parameter for biregular bipartite graphs in the case when $R$ is one of the sides of a bipartition of the graph.

Détail

Keywords: proper edge coloring, interval edge coloring, interval spectrum, biregular bipartite graph.

Bibliographie

[1] A. S. Asratian, Investigation of some mathematical model of Scheduling Theory, Doctoral Dissertation, Moscow University, 1980 (Russian)

[2] A. S. Asratian, C. J. Casselgren, “A sufficient condition for interval edge colorings of $(4,3)$-biregular bipartite graphs”, Research report LiTH-MAT-R-2006-07, Linköping University, 2006

[3] A. S. Asratian, C. J. Casselgren, “Some results on interval edge colorings of $(\alpha,\beta)$-biregular bipartite graphs”, Research report LiTH-MAT-R-2006-09, Linköping University, 2006 | MR

[4] A. S. Asratian, C. J. Casselgren, “On interval edge colorings of $(\alpha,\beta)$-biregular bipartite graphs”, Discrete Math., 307 (2007), 1951–1956 | DOI | MR | Zbl

[5] A. S. Asratian, C. J. Casselgren, J. Vandenbussche, D. B. West, “Proper path-factors and interval edge-coloring of $(3,4)$-biregular bigraphs”, J. of Graph Theory, 61 (2009), 88–97 | DOI | MR | Zbl

[6] A. S. Asratian, T. M. J. Denley, R. Haggkvist, Bipartite graphs and their applications, Cambridge Tracts in Mathematics, 131, Cambridge University Press, 1998 | MR | Zbl

[7] A. S. Asratian, R. R. Kamalian, “Interval colorings of edges of a multigraph”, Appl. Math., 5, Yerevan State University, 1987, 25–34 (Russian) | MR

[8] A. S. Asratian, R. R. Kamalian, “Investigation of interval edge-colorings of graphs”, Journal of Combinatorial Theory. Series B, 62:1 (1994), 34–43 | DOI | MR | Zbl

[9] M. A. Axenovich, “On interval colorings of planar graphs”, Congr. Numer., 159 (2002), 77–94 | MR | Zbl

[10] D. P. Geller and A. J. W. Hilton, “How to color the lines of a bigraph”, Networks, 4 (1974), 281–282 | DOI | MR | Zbl

[11] K. Giaro, Compact task scheduling on dedicated processors with no waiting periods, PhD thesis, Technical University of Gdansk, EIT faculty, Gdansk, 1999 (Polish)

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

[13] K. Giaro, M. Kubale and M. Malafiejski, “On the deficiency of bipartite graphs”, Discrete Appl. Math., 94 (1999), 193–203 | DOI | MR | Zbl

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

[15] D. Hanson, C. O. M. Loten, B. Toft, “On interval colorings of bi-regular bipartite graphs”, Ars Combin., 50 (1998), 23–32 | MR | Zbl

[16] T. R. Jensen, B. Toft, Graph Coloring Problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995 | MR

[17] R. R. Kamalian, Interval Edge Colorings of Graphs, Doctoral dissertation, The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk, 1990 (Russian)

[18] R. R. Kamalian, “On one-sided interval colorings of bipartite graphs”, the Herald of the RAU, 2010, no. 2, 3–11 (Russian)

[19] R. R. Kamalian, Interval colorings of complete bipartite graphs and trees, The Computing Centre of the Academy of Sciences of Armenia, Yerevan, 1989, preprint (Russian)

[20] M. Kubale, Graph Colorings, American Mathematical Society, 2004 | MR | Zbl

[21] P. A. Petrosyan, “Interval edge-colorings of complete graphs and $n$-dimensional cubes”, Discrete Math., 310 (2010), 1580–1587 | DOI | MR | Zbl

[22] P. A. Petrosyan, “On interval edge-colorings of multigraphs”, The Herald of the RAU, 2011, no. 1, 12–21 (Russian)

[23] P. A. Petrosyan, H. H. Khachatrian, “Interval non-edge-colorable bipartite graphs and multigraphs”, J. of Graph Theory, 76 (2014), 200–216 | DOI | MR | Zbl

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

[25] S. V. Sevast'janov, “Interval colorability of the edges of a bipartite graph”, Metody Diskret. Analiza, 50 (1990), 61–72 (Russian) | MR

[26] V. G. Vizing, “The chromatic index of a multigraph”, Kibernetika, 3 (1965), 29–39 | MR | Zbl

[27] D. B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 1996 | MR

[28] F. Yang, X. Li, “Interval coloring of $(3,4)$-biregular bigraphs having two $(2,3)$-biregular bipartite subgraphs”, Appl. Math. Letters, 24 (2011), 1574–1577 | DOI | MR | Zbl

[29] Y. Zhao and J. G. Chang, “Consecutive Edge-Colorings of Generalized $\theta$-Graphs”, CGGA (2010), LNCS, 7033, eds. J. Akiyama et al., 2011, 214–225 | MR | Zbl