NEAR-INTERVAL EDGE-COLORINGS OF COMPLETE BIPARTITE GRAPHS
DOI:
https://doi.org/10.46991/PYSUA.2026.60.1.005Keywords:
proper edge-coloring, near-interval coloring, interval coloring, complete bipartite graphAbstract
A proper edge-coloring of a graph $G$ is a mapping $\alpha:E(G)\longrightarrow \mathbb{N}$ such that $\alpha(e)\not=\alpha(e')$ for every pair of adjacent edges $e$ and $e'$ in $G$. If $\alpha $ is a proper edge-coloring of $G$ and $v\in V(G)$, then $S_{G}\left(v,\alpha \right)$ denotes the set of colors appearing on edges incident to $v$. A proper edge-coloring $\alpha$ of a graph $G$ with colors $1,\ldots,t$ is called a near-interval $t$-coloring if all colors are used, and for each vertex $v\in V(G)$, $S_G(v,\alpha)$ is an interval of integers with no more than one gap. If a graph $G$ has such a coloring, the minimum number of colors in a near-interval coloring of a graph $G$ is denoted by $w^{1}(G)$. It is known that all complete bipartite graphs admit near-interval colorings. In this paper, we determine or bound the parameter $w^{1}(K_{m,n})$ ($m,n\in\mathbb{N}$) for complete bipartite graphs.
Downloads
References
Asratian A.S., Denley T.M.J., Haggkvist R. Bipartite Graphs and their Applications. Cambridge University Press, Cambridge (1998). https://doi.org/10.1017/CBO9780511984068 DOI: https://doi.org/10.1017/CBO9780511984068
West D.B. Introduction to Graph Theory. New Jersey, Prentice-Hall (2001).
Petrosyan P.A., Arakelyan H.Z., Baghdasaryan V.M. A Generalization of Interval Edge-colorings of Graphs. Discrete Appl. Math. 158 (16) (2010), 1827-1837. https://doi.org/10.1016/j.dam.2010.06.012 DOI: https://doi.org/10.1016/j.dam.2010.06.012
Petrosyan P.A., Arakelyan Z. On a Generalization of Interval Edge Colorings of Graphs. Mathematical Problems of Computer Science, 29 (2007), 26-32.
Asratian A.S., Kamalian R.R. Interval Colorings of Edges of a Multigraph. Appl. Math. 5 (1987), 25-34 (in Russian).
Asratian A.S., Kamalian R.R. Investigation on Interval Edge-Colorings of Graphs. J. Combin. Theory Ser. B 62 (1994), 34-43. https://doi.org/10.1006/jctb.1994.1053 DOI: https://doi.org/10.1006/jctb.1994.1053
Jensen T.R., Toft B. Graph Coloring Problems. Wiley, Wiley Series in Discrete Mathematics and Optimization (2011).
Kubale M. Graph Colorings. American Mathematical Society (2004). DOI: https://doi.org/10.1090/conm/352
Stiebitz M., Scheide D., Toft B., Favrholdt L.M. Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture, Wiley (2012).
Petrosyan P.A., Khachatrian H.H., Mamikonyan T.K. On Interval Edge-Colorings of Bipartite Graphs. IEEE Computer Science and Information Technologies (CSIT) (2015), 71-76. https://doi.org/10.1109/CSITechnol.2015.7358253 DOI: https://doi.org/10.1109/CSITechnol.2015.7358253
Casselgren C.J., Toft B. On Interval Edge Colorings of Biregular Bipartite Graphs with Small Vertex Degrees. J. Graph Theory 80 (2) (2015), 83-97. https://doi.org/10.1002/jgt.21841 DOI: https://doi.org/10.1002/jgt.21841
Casselgren C.J., Malafiejski M., Pastuszak K., Petrosyan P.A. Near-interval Edge Colorings of Graphs. Discrete Appl. Math. 372 (2025), 23-36. https://doi.org/10.1016/j.dam.2025.03.011 DOI: https://doi.org/10.1016/j.dam.2025.03.011
Kamalian R.R. Interval Colorings of Complete Bipartite Graphs and Trees. Preprint. Comp. Cen. of Acad. Sci. of Armenian SSR. Yerevan (1989) (in Russian).
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
