Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00002863" target="_blank" >RIV/00216208:11320/06:00002863 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
Original language description
We provide a detailed study of the computational complexity of the problem of coloring a planar graph with the minimum number of colors so that each color class avoids a forbidden graph as a subgraph. We show that the 2-coloring problem is NP-hard if theforbidden graph is a tree with at least two edges, and polynomially solvable otherwise, and the 3-coloring problem is NP-hard if the forbidden graph is a path with at least one edge, and polynomially solvable otherwise.
Czech name
Barvení rovinných grafů vyhýbající se jednobarevným podgrafům: stromy a cesty to dělají složitým
Czech description
Studujeme otázku barvení rovinných grafů tak, aby se v žádné barvě nevyskytl zakázaný podgraf. Ukazujeme, že 2-barvení je NP-úplné v případě, že zakázaným grafem je strom s alespoň dvěma hranami, a polynomiální jinak, zatímco 3-barvení je NP-úplné v případě, že zakázaný graf je cesta s alespoň jednou hranou, a polynomiální jinak.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)