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

Haitze J. Broersma, F.V. Fomin, J. Kratochvil, Gerhard Woeginger

Research output: Book/ReportReportOther research output

7 Downloads (Pure)

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.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 2003

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1701
ISSN (Print)0169-2690

Fingerprint

Coloring
Color
Computational complexity

Keywords

  • MSC-05C85
  • MSC-05C15
  • IR-65886
  • EWI-3521
  • MSC-05C17

Cite this

Broersma, H. J., Fomin, F. V., Kratochvil, J., & Woeginger, G. (2003). Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult. (Memorandum Afdeling TW; No. 1701). Enschede: University of Twente, Department of Applied Mathematics.
Broersma, Haitze J. ; Fomin, F.V. ; Kratochvil, J. ; Woeginger, Gerhard. / Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult. Enschede : University of Twente, Department of Applied Mathematics, 2003. (Memorandum Afdeling TW; 1701).
@book{a5e3d4ed4afd481ca5ed6cdfc4d56042,
title = "Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult",
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.",
keywords = "MSC-05C85, MSC-05C15, IR-65886, EWI-3521, MSC-05C17",
author = "Broersma, {Haitze J.} and F.V. Fomin and J. Kratochvil and Gerhard Woeginger",
note = "Imported from MEMORANDA",
year = "2003",
language = "English",
series = "Memorandum Afdeling TW",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1701",

}

Broersma, HJ, Fomin, FV, Kratochvil, J & Woeginger, G 2003, Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult. Memorandum Afdeling TW, no. 1701, University of Twente, Department of Applied Mathematics, Enschede.

Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult. / Broersma, Haitze J.; Fomin, F.V.; Kratochvil, J.; Woeginger, Gerhard.

Enschede : University of Twente, Department of Applied Mathematics, 2003. (Memorandum Afdeling TW; No. 1701).

Research output: Book/ReportReportOther research output

TY - BOOK

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

AU - Broersma, Haitze J.

AU - Fomin, F.V.

AU - Kratochvil, J.

AU - Woeginger, Gerhard

N1 - Imported from MEMORANDA

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

KW - MSC-05C85

KW - MSC-05C15

KW - IR-65886

KW - EWI-3521

KW - MSC-05C17

M3 - Report

T3 - Memorandum Afdeling TW

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

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Broersma HJ, Fomin FV, Kratochvil J, Woeginger G. Planar graph coloring avoiding monochromatic subgraphs: trees and paths make things difficult. Enschede: University of Twente, Department of Applied Mathematics, 2003. (Memorandum Afdeling TW; 1701).