✦ LIBER ✦

A lower bound for partial list colorings

✍ Scribed by Chappell, Glenn G.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 188 KB
Volume: 32
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199912)32:4<390::aid-jgt6>3.0.co;2-d

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be an n-vertex graph with list-chromatic number χ . Suppose that each vertex of G is assigned a list of t colors. Albertson, Grossman, and Haas [1] conjecture that at least t n /χ vertices can be colored from these lists. We prove a lower bound for the number of colorable vertices. As a corollary, we show that at least 6 7 of the conjectured number can be colored.

📜 SIMILAR VOLUMES

A lower bound for groupies in graphs

✍ Mackey, John 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 2 views

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contai

A lower bound for interval routing in ge

A lower bound for interval routing in general networks

✍ Tse, Savio S. H.; Lau, Francis C. M. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of t

A lower bound for the crossing number of

A lower bound for the crossing number of Cm × Cn

✍ Gelasio Salazar 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

A strong lower bound for the Node Weight

A strong lower bound for the Node Weighted Steiner Tree Problem

✍ Engevall, Stefan; G�the-Lundgren, Maud; V�rbrand, Peter 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 84 KB 👁 1 views

In this paper, we study the Node Weighted Steiner Tree Problem (NSP). This problem is a generalization of the Steiner tree problem in the sense that vertex weights are considered. Given an undirected graph, the problem is to find a tree that spans a subset of the vertices and is such that the total

A fast and accurate method for determini

A fast and accurate method for determining a lower bound on execution time

✍ G. Fursin; M. F. P. O'Boyle; O. Temam; G. Watts 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB

## Abstract In performance critical applications, memory latency is frequently the dominant overhead. In many cases, automatic compiler‐based optimizations to improve memory performance are limited and programmers frequently resort to manual optimization techniques. However, this process is tedious

A nonlinear programming approach to lowe

A nonlinear programming approach to lower bounds for the ground-state energy of helium

✍ I. Porras; D. Matthew Feldmann; Frederick W. King 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB 👁 2 views

Lower-bound estimates for the ground-state energy of the helium atom are determined using nonlinear programming techniques. Optimized lower bounds are determined for single-particle, radially correlated, and general correlated wave functions. The local nature of the method employed makes it a very s