✦ LIBER ✦

A Note on First-Fit Coloring of Interval Graphs

✍ Scribed by N. S. Narayanaswamy; R. Subhash Babu

Publisher: Springer Netherlands
Year: 2008
Tongue: English
Weight: 223 KB
Volume: 25
Category: Article
ISSN: 0167-8094
DOI: 10.1007/s11083-008-9076-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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.

On-line and first fit colorings of graph

On-line and first fit colorings of graphs

✍ A. Gyárfás; J. Lehel 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 537 KB

A graph coloring algorithm that immediately colors the vertices taken from a list without looking ahead or changing colors already assigned is called "on-line coloring." The properties of on-line colorings are investigated in several classes of graphs. In many cases w e find on-line colorings that u

A note on list improper coloring planar

A note on list improper coloring planar graphs

✍ Ko-Wei Lih; Zengmin Song; Weifan Wang; Kemin Zhang 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 267 KB

A graph G is called (k, d)\*-choosable if, for every list assignment L satisfying [L(v)l = k for all v E V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this note, we prove that every planar graph without 4-cycles and /-c

A Note on Graph Colorings and Graph Poly

A Note on Graph Colorings and Graph Polynomials

✍ Noga Alon; Michael Tarsi 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 230 KB

## dedicated to professor w. t. tutte on the occasion of his eightieth birtday It is known that the chromatic number of a graph G=(V, E) with V= [1, 2, ..., n] exceeds k iff the graph polynomial f G => ij # E, i<j (x i &x j ) lies in certain ideals. We describe a short proof of this result, using

A note on local colorings of graphs

✍ Andrzej Ruciński; Miroslaw Truszczyński 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 223 KB

Recently, R6dl and Rucifiski [5,6] proved the following threshold result about Ramsey properties of random graphs. Let K(n, p) be the binomial random graph obtained from the complete graph K(n) by independent deletion of each edge with probability 1 -p. We write F ~ (G)r if for every r-coloring of t

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