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

Share/Save/Bookmark

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]

open access
[img]
Preview
PDF
262kB
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
Additional information:Imported from MEMORANDA
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65886
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page