✦ LIBER ✦

Extending an edge-coloring

✍ Scribed by O. Marcotte; P. D. Seymour

Publisher: John Wiley and Sons
Year: 1990
Tongue: English
Weight: 354 KB
Volume: 14
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190140508

No coin nor oath required. For personal study only.

✦ Synopsis

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 edges of K colored i is a matching. This condition is not sufficient in general, but is sufficient for graphs of very simple structure. We try to locate the border where sufficiency ends.

📜 SIMILAR VOLUMES

An edge coloring problem for graph produ

An edge coloring problem for graph products

✍ Faudree, R. J.; Gy�rf�s, Andr�as; Schelp, R. H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 315 KB 👁 1 views

The edges of the Cartesian product of graphs G x H a r e to be colored with the condition that all rectangles, i.e., K2 x K2 subgraphs, must be colored with four distinct colors. The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H

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

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

Edge-Coloring Partialk-Trees

✍ Xiao Zhou; Shin-ichi Nakano; Takao Nishizeki 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 278 KB

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

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

An NC Parallel Algorithm for Edge-Colori

An NC Parallel Algorithm for Edge-Coloring Series–Parallel Multigraphs

✍ Xiao Zhou; Hitoshi Suzuki; Takao Nishizeki 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Many combinatorial problems can be efficiently solved in parallel for series᎐parallel multigraphs. The edge-coloring problem is one of a few combinatorial problems for which no NC parallel algorithm has been obtained for series᎐parallel multigraphs. This paper gives an NC parallel algorithm for the