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

Abstract

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

How to cite

top

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 -

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.