𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the cost-chromatic number of graphs

✍ Scribed by John Mitchem; Patrick Morriss

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
566 KB
Volume
171
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider vertex colorings in which each color has an associated cost, incurred each time the color is assigned to a vertex. For a given set of costs, a minimum-cost coloring is a vertex coloring which makes the total cost of coloring the graph as small as possible. The cost-chromatic number of a graph with respect to a cost set is the minimum number of colors necessary to produce a minimum-cost coloring of the graph.

We establish upper bounds on the cost-chromatic number, show that trees and planar blocks can have arbitrarily large cost-chromatic number, and show that cost-chromatic number is not monotonic with subgraph inclusion.

πŸ“œ SIMILAR VOLUMES

On the chromatic number of disk graphs
On the chromatic number of disk graphs
✍ Malesi?ska, Ewa; Piskorz, Steffen; WeiοΏ½enfels, Gerhard πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 172 KB πŸ‘ 2 views

Colorings of disk graphs arise in the study of the frequency-assignment problem in broadcast networks. Motivated by the observations that the chromatic number of graphs modeling real networks hardly exceeds their clique number, we examine the related properties of the unit disk (UD) graphs and their

On the chromatic number of cube-like gra
On the chromatic number of cube-like graphs
✍ Charles Payan πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 343 KB

A cube-like graph is a graph whose vertices are all 2" subsets of a set E of cardinality n, in which two vertices are adjacent if their symmetric difference is a member of a given specified collection of subsets of E. Many authors were interested in the chromatic number of such graphs and thought it

On the chromatic number of special dista
On the chromatic number of special distance graphs
✍ M. Voigt; H. Walther πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 153 KB

## A b&act Voigt, M. and H. Walther, On the chromatic number of special distance graphs, Discrete Mathematics 97 (1991) 395-397. For all 12 10 and u 2 1' -61+ 3 the chromatic number is proved to be 3 for distance graphs with all integers as vertices, and edges only if the vertices are at distance

On bounding the chromatic number of L-gr
On bounding the chromatic number of L-graphs
✍ Sean McGuinness πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 585 KB

We show that the intersection graph of a collection of subsets of the plane, where each subset forms an "L" shape whose vertical stem is infinite, has its chromatic number 1 bounded by a function of the order of its largest clique w, where it is shown that ;1<2"4'3"4"'~'-". This proves a special cas

On the chromatic number of integral circ
On the chromatic number of integral circulant graphs
✍ Aleksandar IliΔ‡; Milan BaΕ‘iΔ‡ πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 395 KB

Integral circulant graphs are a generalization of unitary Cayley graphs, recently studied by Klotz and Sander. The integral circulant graph X n (D) has vertices 0, 1, . . . , n -1, and two vertices a and b are adjacent iff gcd(xy, n) ∈ D, where D βŠ† {d : Circulant graphs have various applications in