𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Coloring interval graphs with first-fit

✍ Scribed by H.A. Kierstead; Jun Qin

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
569 KB
Volume
144
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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

πŸ“œ SIMILAR VOLUMES

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

Interval edge coloring of a graph with f
Interval edge coloring of a graph with forbidden colors
✍ Marek Kubale πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 596 KB

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

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 Graphs with Sparse Neighborhood
Coloring Graphs with Sparse Neighborhoods
✍ Noga Alon; Michael Krivelevich; Benny Sudakov πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 118 KB

It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 Γ‚f is at most O(dΓ‚log f ). This is tight (up to a constant factor) for all admissible values of d and f.

Interval coloring of (3,4)-biregular bip
Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs
✍ A. V. Pyatkin πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 80 KB

## Abstract An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph __G__ = (__A__,__B__;__E__) is (Ξ±, Ξ²)‐b