Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult

Broersma, H.J. and Fomin, F.V. and Kratochvil, J. and Woeginger, G.J. (2003) Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult. [Report]

Preview

PDF
256Kb

Abstract:	We consider the problem of coloring a planar graph with the minimum number of colors such that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem.
Item Type:	Report
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/65886
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page