# WORM Colorings of Planar Graphs

J. Czap; S. Jendrol’; J. Valiska

Discussiones Mathematicae Graph Theory (2017)

- Volume: 37, Issue: 2, page 353-368
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJ. Czap, S. Jendrol’, and J. Valiska. "WORM Colorings of Planar Graphs." Discussiones Mathematicae Graph Theory 37.2 (2017): 353-368. <http://eudml.org/doc/288003>.

@article{J2017,

abstract = {Given three planar graphs F,H, and G, an (F,H)-WORM coloring of G is a vertex coloring such that no subgraph isomorphic to F is rainbow and no subgraph isomorphic to H is monochromatic. If G has at least one (F,H)-WORM coloring, then W−F,H(G) denotes the minimum number of colors in an (F,H)-WORM coloring of G. We show that (a) W−F,H(G) ≤ 2 if |V (F)| ≥ 3 and H contains a cycle, (b) W−F,H(G) ≤ 3 if |V (F)| ≥ 4 and H is a forest with Δ (H) ≥ 3, (c) W−F,H(G) ≤ 4 if |V (F)| ≥ 5 and H is a forest with 1 ≤ Δ (H) ≤ 2. The cases when both F and H are nontrivial paths are more complicated; therefore we consider a relaxation of the original problem. Among others, we prove that any 3-connected plane graph (respectively outerplane graph) admits a 2-coloring such that no facial path on five (respectively four) vertices is monochromatic.},

author = {J. Czap, S. Jendrol’, J. Valiska},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {plane graph; monochromatic path; rainbow path; WORM coloring; facial coloring},

language = {eng},

number = {2},

pages = {353-368},

title = {WORM Colorings of Planar Graphs},

url = {http://eudml.org/doc/288003},

volume = {37},

year = {2017},

}

TY - JOUR

AU - J. Czap

AU - S. Jendrol’

AU - J. Valiska

TI - WORM Colorings of Planar Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2017

VL - 37

IS - 2

SP - 353

EP - 368

AB - Given three planar graphs F,H, and G, an (F,H)-WORM coloring of G is a vertex coloring such that no subgraph isomorphic to F is rainbow and no subgraph isomorphic to H is monochromatic. If G has at least one (F,H)-WORM coloring, then W−F,H(G) denotes the minimum number of colors in an (F,H)-WORM coloring of G. We show that (a) W−F,H(G) ≤ 2 if |V (F)| ≥ 3 and H contains a cycle, (b) W−F,H(G) ≤ 3 if |V (F)| ≥ 4 and H is a forest with Δ (H) ≥ 3, (c) W−F,H(G) ≤ 4 if |V (F)| ≥ 5 and H is a forest with 1 ≤ Δ (H) ≤ 2. The cases when both F and H are nontrivial paths are more complicated; therefore we consider a relaxation of the original problem. Among others, we prove that any 3-connected plane graph (respectively outerplane graph) admits a 2-coloring such that no facial path on five (respectively four) vertices is monochromatic.

LA - eng

KW - plane graph; monochromatic path; rainbow path; WORM coloring; facial coloring

UR - http://eudml.org/doc/288003

ER -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.