A Note on Edge Coloring of Graphs

作者：Akbari S^*; Iradmusa M N; Jamaali M

来源：Ars Combinatoria, 2015, 119: 289-292.

• Edge coloring

Let G be a graph of minimum degree delta(G). R.P. Gupta proved the two following interesting results: 1) A bipartite graph G has a delta-edge-coloring in which all delta colors appear at each vertex. 2) If G is a simple graph with delta(G) > 1, then G has a (delta - 1)-edge-coloring in which all (delta - 1) colors appear at each vertex. Let t be a positive integer. In this paper, we extend the first result by showing that for every bipartite graph, there exists a t-edge coloring such that, at each vertex v, min{t, d(v)} colors appear. Also, we show that if G is a graph, then the edges of G can be colored using t colors in which for each vertex v, the number of colors appear at v is at least min{t, d(v) - 1}, which generalizes the second result.

• 出版日期2015-1