✦ LIBER ✦

Edge-Coloring Partialk-Trees

✍ Scribed by Xiao Zhou; Shin-ichi Nakano; Takao Nishizeki

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 278 KB
Volume: 21
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0061

No coin nor oath required. For personal study only.

✦ Synopsis

Many combinatorial problems can be efficiently solved for partial k-trees graphs . of treewidth bounded by k . The edge-coloring problem is one of the well-known combinatorial problems for which no efficient algorithms were previously known, except a polynomial-time algorithm of very high complexity. This paper gives a linear-time sequential algorithm and an optimal parallel algorithm which find an edge-coloring of a given partial k-tree with the minimum number of colors for fixed k.

📜 SIMILAR VOLUMES

Edge coloring a k-tree into two smaller

Edge coloring a k-tree into two smaller trees

✍ Chhajed, Dilip 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 56 KB

The problem of the edge coloring partial k-tree into two partial p-and q-trees with p, q õ k is considered. An algorithm is provided to construct such a coloring with p / q Å k. Usefulness of this result in a Lagrangian decomposition framework to solve certain combinatorial optimization problems is

Equitable Coloring of Trees

✍ B.L. Chen; K.W. Lih 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 224 KB

A graph is equitably \(k\)-colorable if its vertices can be partitioned into \(k\) independent sets of as near equal sizes as possible. Regarding a non-null tree \(T\) as a bipartite graph \(T(X, Y)\), we show that \(T\) is equitably \(k\)-colorable if and only if (i) \(k \geqslant 2\) when ||\(X|-|

Parallel Algorithms for the Edge-Colorin

Parallel Algorithms for the Edge-Coloring and Edge-Coloring Update Problems

✍ Weifa Liang; Xiaojun Shen; Qing Hu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 342 KB

In fact, Vizing's proof implies an O(nm) time algorithm with ⌬ ϩ 1 colors for the edge-coloring problem. However, Holyer has shown that deciding whether a graph requires ⌬ or ⌬ ϩ 1 colors is NP-complete [10]. For a multigraph G, Shannon showed that Ј(G) Յ 3⌬/2 [16]. A number of parallel algorithms

Extending an edge-coloring

✍ O. Marcotte; P. D. Seymour 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 354 KB

## Abstract When can a __k__‐edge‐coloring of a subgraph __K__ of a graph __G__ be extended to a __k__‐edge‐coloring of __G__? One necessary condition is that for all __X ⊆ E__(__G__) ‐ __E__(__K__), where μ~i~(__X__) is the maximum cardinality of a subset of __X__ whose union with the set of edg

Edge-Coloring Bipartite Graphs

✍ Ajai Kapoor; Romeo Rizzi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 65 KB

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 th

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