✦ LIBER ✦

Interval edge coloring of a graph with forbidden colors

✍ Scribed by Marek Kubale

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 596 KB
Volume: 121
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90546-6

No coin nor oath required. For personal study only.

✦ Synopsis

This paper is complementary

to Kubale (1989). We consider herein a problem of interval coloring the edges of a graph under the restriction that certain colors cannot be used for some edges. We give lower and upper bounds on the minimum number of colors required for such a coloring. Since the general problem is strongly NP-complete, we investigate its complexity in some special cases with particular reference to those that can be solved by polynomial-time algorithms.

📜 SIMILAR VOLUMES

Investigation on Interval Edge-Colorings

Investigation on Interval Edge-Colorings of Graphs

✍ A.S. Asratian; R.R. Kamalian 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 380 KB

An edge-coloring of a simple graph \(G\) with colors \(1,2, \ldots, t\) is called an interval \(t\)-coloring [3] if at least one edge of \(G\) is colored by color \(i, i=1, \ldots, t\) and the edges incident with each vertex \(x\) are colored by \(d_{G}(x)\) consecutive colors, where \(d_{G}(x)\) is

Coloring interval graphs with first-fit

✍ H.A. Kierstead; Jun Qin 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 569 KB

Improved bounds on the performance of the on-line graph coloring algorithm First-Fit on interval graphs are obtained.

Coloring a graph optimally with two colo

Coloring a graph optimally with two colors

✍ H.J. Broersma; F. Göbel 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 536 KB

Let G be a graph with point set V. A (2.)c,oloring of G is a map of V to ired, white!. An error occurs whenever the two endpoints of a line have the same color. An oprimul doring of G is a coloring of G for which the number of errors is minimum. The minimum number of errors is denoted by y(G), we de

Even edge colorings of a graph

✍ B. Devadas Acharya 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 78 KB

Even edge colorings of a graph

✍ Noga Alon; Yoshimi Egawa 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 59 KB

Coloring edges of embedded graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

In this paper, we prove that any graph G with maximum degree ÁG ! 11 p 49À241AEa2, which is embeddable in a surface AE of characteristic 1AE 1 and satis®es jVGj b 2ÁGÀ5À2 p 6ÁG, is class one.