Parsimonious edge coloring (Q1910535)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parsimonious edge coloring |
scientific article |
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