✦ LIBER ✦

Coloring precolored perfect graphs

✍ Scribed by Kratochv�l, Jan; Seb?, Andr�s

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 115 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199707)25:3<207::aid-jgt4>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the question of the computational complexity of coloring perfect graphs with some precolored vertices. It is well known that a perfect graph can be colored optimally in polynomial time. Our results give a sharp border between the polynomial and NP-complete instances, when precolored vertices occur. The key result on the polynomially solvable cases includes a good characterization theorem on the existence of an optimal coloring of a perfect graph where a given stable set is precolored with only one color. The key negative result states that the 3-colorability of a graph whose odd circuits go through two fixed vertices is NP-complete. The polynomial algorithms use Grötschel, Lovász and Schrijver's algorithm for finding a maximum clique in a graph, but are otherwise purely combinatorial.

📜 SIMILAR VOLUMES

Coloring edges of embedded graphs

✍ Daniel P. Sanders; Yue Zhao 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 1 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.

Coloring graphs which have equibipartite

Coloring graphs which have equibipartite complements

✍ Hilton, A. J. W.; Zhao, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 205 KB

If G is a graph of order 2n ≥ 4 with an equibipartite complement, then G is Class 1 (i.e., the chromatic index of G is ∆(G)) if and only if G is not the union of two disjoint K n 's with n odd. Similarly if G is a graph of order 2n ≥ 6 whose complement Ḡ is equibipartite with bipartition (A, D), and

Optimal edge coloring of large graphs

✍ G�mez, J.; Escudero, M. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 2 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

Algorithms for coloring semi-random grap

Algorithms for coloring semi-random graphs

✍ C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 2 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co

3-Coloring graphs embedded in surfaces

✍ Zhao, Yue 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB 👁 2 views

In this article, we show that there exists an integer k(Σ)

Cycle-perfect graphs are perfect

✍ Le, Van Bang 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB 👁 2 views

The cycle graph of a graph G is the edge intersection graph of the set of all the induced cycles of G. G is called cycle-perfect if G and its cycle graph have no chordless cycles of odd length at least five. We prove the statement of the title. 0 1996 John Wiley &