کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419541 | 683834 | 2010 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Decompositions for edge-coloring join graphs and cobipartite graphs Decompositions for edge-coloring join graphs and cobipartite graphs](/preview/png/419541.png)
An edge-coloring is an association of colors to the edges of a graph, in such a way that no pair of adjacent edges receive the same color. A graph GG is Class 1 if it is edge-colorable with a number of colors equal to its maximum degree Δ(G)Δ(G). To determine whether a graph GG is Class 1 is NP-complete [I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720]. First, we propose edge-decompositions of a graph GG with the goal of edge-coloring GG with Δ(G)Δ(G) colors. Second, we apply these decompositions for identifying new subsets of Class 1 join graphs and cobipartite graphs. Third, the proposed technique is applied for proving that the chromatic index of a graph is equal to the chromatic index of its semi-core, the subgraph induced by the maximum degree vertices and their neighbors. Finally, we apply these decomposition tools to a classical result [A.J.W. Hilton, Z. Cheng, The chromatic index of a graph whose core has maximum degree 2, Discrete Math. 101 (1992) 135–147] that relates the chromatic index of a graph to its core, the subgraph induced by the maximum degree vertices.
Journal: Discrete Applied Mathematics - Volume 158, Issue 12, 28 June 2010, Pages 1336–1342