WORM Colorings of Planar Graphs

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