✦ LIBER ✦

Edge-Coloring Bipartite Graphs

✍ Scribed by Ajai Kapoor; Romeo Rizzi

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 65 KB
Volume: 34
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1999.1058

No coin nor oath required. For personal study only.

✦ Synopsis

Given a bipartite graph G with n nodes, m edges, and maximum degree ⌬, we Ž . find an edge-coloring for G using ⌬ colors in time T q O m log ⌬ , where T is the time needed to find a perfect matching in a k-regular bipartite graph with Ž . O m edges and k F ⌬. Together with best known bounds for T this implies m m 2 Ž . on O m log ⌬ q log log ⌬ edge-coloring algorithm which improves on the ⌬ ⌬ m m 3 Ž . O m log ⌬ q log log ⌬ algorithm of Hopcroft and Cole. Our algorithm can ⌬ ⌬ Ž .

Ž . also be used to find a ⌬ q 2 -edge-coloring for G in time O m log ⌬ . The previous best approximation algorithm with the same time bound needed ⌬ q log ⌬ colors.

📜 SIMILAR VOLUMES

Star coloring bipartite planar graphs

✍ H. A. Kierstead; André Kündgen; Craig Timmons 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB

## Abstract A __star coloring__ of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eig

Balanced coloring of bipartite graphs

✍ Uriel Feige; Shimon Kogan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Given a bipartite graph __G__(__U__∪__V, E__) with __n__ vertices on each side, an independent set __I__∈__G__ such that |__U__∩__I__|=|__V__∩__I__| is called a balanced bipartite independent set. A balanced coloring of __G__ is a coloring of the vertices of __G__ such that each color c

Coloring Locally Bipartite Graphs on Sur

Coloring Locally Bipartite Graphs on Surfaces

✍ Bojan Mohar; Paul D. Seymour 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 129 KB

It is proved that there is a function f: N Q N such that the following holds. Let G be a graph embedded in a surface of Euler genus g with all faces of even size and with edge-width \ f(g). Then (i) If every contractible 4-cycle of G is facial and there is a face of size > 4, then G is 3-colorable.

Semistrong edge coloring of graphs

✍ András Gyárfás; Alice Hubenko 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract Weakening the notion of a strong (induced) matching of graphs, in this paper, we introduce the notion of a semistrong matching. A matching __M__ of a graph __G__ is called semistrong if each edge of __M__ has a vertex, which is of degree one in the induced subgraph __G__[__M__]. We stre

Optimal edge coloring of large graphs

✍ G�mez, J.; Escudero, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 3 views

Most of the general families of large considered graphs in the context of the so-called (⌬, D) problem-that is, how to obtain graphs with maximum order, given their maximum degree ⌬ and their diameter D-known up to now for any value of ⌬ and D, are obtained as product graphs, compound graphs, and ge

Minimum Color Sum of Bipartite Graphs

✍ Amotz Bar-Noy; Guy Kortsarz 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 242 KB

The problem of minimum color sum of a graph is to color the vertices of the Ž . graph such that the sum average of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated within 1y ⑀ Ž n , for any ⑀ ) 0, unless NP s ZPP Bar-Noy et al., Informa