𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation results for the minimum graph coloring problem

✍ Scribed by Marc Demange; Pascal Grisoni; Vangelis Th. Paschos

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
381 KB
Volume
50
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An edge coloring problem for graph produ
An edge coloring problem for graph products
✍ Faudree, R. J.; GyοΏ½rfοΏ½s, AndrοΏ½as; Schelp, R. H. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 315 KB πŸ‘ 1 views

The edges of the Cartesian product of graphs G x H a r e to be colored with the condition that all rectangles, i.e., K2 x K2 subgraphs, must be colored with four distinct colors. The minimum number of colors in such colorings is determined for all pairs of graphs except when G is 5-chromatic and H

Algorithms for the minimum partitioning
Algorithms for the minimum partitioning problems in graphs
✍ Hiroshi Nagamochi πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 545 KB

## Abstract In this paper, the author explains the recent evolution of algorithms for minimum partitioning problems in graphs. When the set of vertices of a graph having non‐negative weights for edges is divided into __k__ subsets, the set of edges for which both endpoints are contained in differen

Minimum bandwidth problem for embedding
Minimum bandwidth problem for embedding graphs in cycles
✍ Lin, Yixun πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 98 KB πŸ‘ 2 views

For the bandwidth B(G) and the cyclic bandwidth B c (G) of a graph G, it is known that 1 2 B(G) Β°Bc (G) Β°B(G). In this paper, the criterion conditions for two extreme cases B c (G) Γ… B(G) and B c (G) Γ… 1 2 B(G) are studied. From this, some exact values of B c (G) for special graphs can be obtained.