One-sided interval edge-colorings of bipartite graphs

详细信息    查看全文

• 作者：Carl Johan Casselgren^a ; ¹ ; ^{carl.johan.casselgren@liu.se" class="auth_mail" title="E-mail the corresponding author} ; Bjarne Toft^b ; ^{btoft@imada.sdu.dk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Interval edge-coloring ; Bipartite graph ; Edge coloring
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 November 2016
• 年：2016
• 卷：339
• 期：11
• 页码：2628-2639
• 全文大小：434 K

文摘

Let 547665b" title="Click to view the MathML source">G$G$ be a bipartite graph with bipartition (X,Y)$(X,Y)$. An X$X$-interval coloring of 547665b" title="Click to view the MathML source">G$G$ is a proper edge-coloring of 547665b" title="Click to view the MathML source">G$G$ by integers such that the colors on the edges incident to any vertex in X$X$ form an interval. Denote by ${\chi }_{int}^{\prime }(G,X)$ the minimum e178e8d721ca94cd95e5c174b11" title="Click to view the MathML source">k$k$ such that 547665b" title="Click to view the MathML source">G$G$ has an X$X$-interval coloring with e178e8d721ca94cd95e5c174b11" title="Click to view the MathML source">k$k$ colors. In this paper we give various upper and lower bounds on ${\chi }_{int}^{\prime }(G,X)$ in terms of the vertex degrees of 547665b" title="Click to view the MathML source">G$G$. We also determine ${\chi }_{int}^{\prime }(G,X)$ exactly for some classes of bipartite graphs 547665b" title="Click to view the MathML source">G$G$. Furthermore, we present upper bounds on ${\chi }_{int}^{\prime }(G,X)$ for classes of bipartite graphs 547665b" title="Click to view the MathML source">G$G$ with maximum degree 54" title="Click to view the MathML source">Δ(G)$\Delta \left(G\right)$ at most 9$9$: in particular, if 4e1b90bcd7cae4099537866" title="Click to view the MathML source">Δ(G)=4$\Delta \left(G\right)=4$, then ${\chi }_{int}^{\prime }(G,X)\le 6$; if Δ(G)=5$\Delta \left(G\right)=5$, then ${\chi }_{int}^{\prime }(G,X)\le 15$; if Δ(G)=6$\Delta \left(G\right)=6$, then ${\chi }_{int}^{\prime }(G,X)\le 33$.