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/

[1] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711-712. doi: 10.1090/S0002-9904-1976-14122-5

[2] M. Axenovich, T. Ueckerdt and P. Weiner, Splitting planar graphs of girth 6 into two linear forests with short paths, arXiv:1507.02815, 2015.

[3] D.W. Barnette, Trees in polyhedral graphs, Canad. J. Math. 18 (1966) 731-736. doi: 10.4153/CJM-1966-073-4

[4] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). doi: 10.1007/978-1-84628-970-5

[5] O.V. Borodin, A. Kostochka and M. Yancey, On 1-improper 2-coloring of sparse graphs, Discrete Math. 313 (2013) 2638-2649. doi: 10.1016/j.disc.2013.07.014

[6] H. Broersma, F.V. Fomin, J. Kratochv´ıl and G.J. Woeginger, Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult, Algorithmica 44 (2006) 343-361. doi: 10.1007/s00453-005-1176-8

[7] Cs. Bujtás, E. Sampathkumar, Zs. Tuza, C. Dominic and L. Pushpalatha, Vertex coloring without large polychromatic stars, Discrete Math. 312 (2012) 2102-2108. doi: 10.1016/j.disc.2011.04.013

[8] Cs. Bujtás, E. Sampathkumar, Zs. Tuza, M.S. Subramanya and C. Dominic, 3- consecutive C-colorings of graphs, Discuss. Math. Graph Theory 30 (2010) 393-405. doi: 10.7151/dmgt.1502

[9] Cs. Bujtás and Zs. Tuza, F-WORM colorings: Results for 2-connected graphs, arXiv:1512.00478, 2015.

[10] Cs. Bujtás and Zs. Tuza, K3-WORM coloring of graphs: Lower chromatic number and gaps in the chromatic spectrum, Discuss. Math. Graph Theory 36 (2016) 759-772. doi: 10.7151/dmgt.1891

[11] G. Chartrand, D.P. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Camb. Phil. Soc. 64 (1968) 265-271. doi: 10.1017/S0305004100042808

[12] G. Chartrand, D.P. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Comb. Theory Ser. B 10 (1971) 12-41. doi: 10.1016/0095-8956(71)90065-7

[13] L. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited, J. Graph Theory 24 (1997) 205-219. doi: 10.1002/(SICI)1097-0118(199703)24:3h205::AID-JGT2i3.0.CO;2-T

[14] Z. Dvořák and D. Král’, On planar mixed hypergraphs, Electron. J. Combin. 8 (2001) R35.

[15] L. Esperet and G. Joret, Colouring planar graphs with three colours and no large monochromatic components, Combin. Probab. Comput. 23 (2014) 551-570. doi: 10.1017/S0963548314000170

[16] H.J. Fleischner, D.P. Geller and F. Harary, Outerplanar graphs and weak duals, J. Indian Math. Soc. 38 (1974) 215-219.

[17] T.-S. Fung, A colourful path, Math. Gaz. 73 (1989) 186-188. doi: 10.2307/3618435

[18] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci. 1 (1976) 237-267. doi: 10.1016/0304-3975(76)90059-1

[19] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94. doi: 10.1016/0012-365X(91)90166-Y

[20] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173.

[21] W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571-584. doi: 10.7151/dmgt.1814

[22] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Universit¨at, Halle-Wittenberg, Math.-Nat. Reihe 8 (1959) 109-120.

[23] D. Kobler and A. Kündgen, Gaps in the chromatic spectrum of face-constrained plane graphs, Electron. J. Combin. 8 (2001) N3.

[24] A. Kündgen, E. Mendelsohn and V. Voloshin, Colouring planar mixed hypergraphs, Electron. J. Combin. 7 (2000) R60.

[25] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238.

[26] K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73-75. doi: 10.1002/jgt.3190140108

[27] B. Roy, Nombre chromatique et plus longs chemins d’un graphe, Rev. Franc. Inform. Rech. Opér. 1 (1967) 129-132.

[28] Zs. Tuza, Graph colorings with local constraints-a survey, Discuss. Math. Graph Theory 17 (1997) 161-228. doi: 10.7151/dmgt.1049

[29] V.I. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45-52.