✦ LIBER ✦

Parsimonious edge coloring

✍ Scribed by Michael O. Albertson; Ruth Haas

Book ID: 103060408
Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 368 KB
Volume: 148
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00254-g

No coin nor oath required. For personal study only.

✦ Synopsis

In a graph G of maximum degree A, let y denote the largest fraction of edges that can be A-edge-colored. This paper investigates lower bounds for 7 together with infinite families of 13 graphs in which y is bounded away from 1. For instance, if G is cubic, then 7 >i ]7; and there _<25 exists an infinite family of 3-connected cubic graphs in which 7 ~ 27.

📜 SIMILAR VOLUMES

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 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

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 of multigraphs

✍ Martin Kochol; Nad’a Krivoňáková; Silvia Smejová 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 167 KB

Mixed graph edge coloring

✍ Hanna Furmańczyk; Adrian Kosowski; Bernard Ries; Paweł Żyliński 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 987 KB