Geodesic
WORM Colorings of Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 353-368

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: plane graph, monochromatic path, rainbow path, WORM coloring, facial coloring 
@article{DMGT_2017_37_2_a3,
     author = {Czap, J. and Jendrol{\textquoteright}, S. and Valiska, J.},
     title = {WORM {Colorings} of {Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {353--368},
     publisher = {mathdoc},
     volume = {37},
     number = {2},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a3/}
}
TY  - JOUR
AU  - Czap, J.
AU  - Jendrol’, S.
AU  - Valiska, J.
TI  - WORM Colorings of Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 353
EP  - 368
VL  - 37
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a3/
LA  - en
ID  - DMGT_2017_37_2_a3
ER  - 
%0 Journal Article
%A Czap, J.
%A Jendrol’, S.
%A Valiska, J.
%T WORM Colorings of Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 353-368
%V 37
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a3/
%G en
%F DMGT_2017_37_2_a3
Czap, J.; Jendrol’, S.; Valiska, J. WORM Colorings of Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 2, pp. 353-368. http://geodesic.mathdoc.fr/item/DMGT_2017_37_2_a3/