Parsimonious edge coloring (Q1910535)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Parsimonious edge coloring |
scientific article; zbMATH DE number 858072
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Parsimonious edge coloring |
scientific article; zbMATH DE number 858072 |
Statements
Parsimonious edge coloring (English)
0 references
24 March 1996
0 references
The authors investigate the largest fraction of edges in a 3-regular graph that can be colored in 3 colors. They show that this fraction is always at least 13/15 and sometimes at most 25/27. They investigate the analogous problem for graphs of maximum degree 3 and also for 4-regular graphs with 4 colors instead of 3.
0 references
edge coloring
0 references
fraction of edges
0 references
colors
0 references
0.94047374
0 references
0.88677204
0 references
0 references
0 references
0.8768226
0 references
0 references
0.87551403
0 references
0 references
