WORM Colorings of Planar Graphs

• Autorzy: J. Czap , S. Jendrol’ , J. Valiska
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 2
• Strony: 353-368

Daty

wydano

2017-05-01

otrzymano

2015-12-03

poprawiono

2016-01-22

zaakceptowano

2016-02-22

online

2017-04-01

Twórcy

autor

J. Czap

• Department of Applied Mathematics and Business Informatics Faculty of Economics, Technical University of Košice Němcovej 32, 040 01 Košice,

autor

S. Jendrol’

• Institute of Mathematics, P.J. Šafárik University Jesenná 5, 040 01 Košice,

autor

J. Valiska

• Institute of Mathematics, P.J. Šafárik University Jesenná 5, 040 01 Košice,

Identyfikatory

DOI

10.7151/dmgt.1921