Parsimonious edge coloring
type: Item
instance of: scholarly article
title: Parsimonious edge coloring
zbMATH Open document ID: 0845.05036
DOI: 10.1016/0012-365X(94)00254-G
author: Ruth Haas
author: Michael O. Albertson
published in: Discrete Mathematics
publication date: 1996-03-24T00:00:00Z
review text: 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.
reviewed by: Carsten Thomassen
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 858072
zbMATH Keywords: edge coloring
zbMATH Keywords: fraction of edges
zbMATH Keywords: colors
MaRDI profile type: Publication
cites work: Largest bipartite subgraphs in triangle-free graphs with maximum degree three
cites work: Short Proof of a Map-Colour Theorem
cites work: Q3853641
cites work: Q4014299
cites work: Extremal bipartite subgraphs of cubic triangle-free graphs
cites work: Maximumk-colorable subgraphs
cites work: On Tutte's extension of the four-colour problem
cites work: Q3898517
cites work: Five-coloring maps on surfaces
Recommended article: Parsimonious edge-coloring on surfaces
Recommended article: A polyhedral approach to edge coloring
Recommended article: Edge homogeneous colorings
Recommended article: Edge colouring by total labellings
Recommended article: Minimum number of palettes in edge colorings
Recommended article: On vertex-parity edge-colorings
Recommended article: Coloring Graphs with Minimal Edge Load
Recommended article: Q4250737
Recommended article: Q4014299
Recommended article: Coloring edges of embedded graphs
description: scientific article; zbMATH DE number 858072