×

WORM colorings of planar graphs. (English) Zbl 1359.05037

Summary: 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)\leq 2\) if \(|V(F)|\geq3\) and \(H\) contains a cycle,
(b)
\(W^{-}_{F,H}(G)\leq3\) if \(|V (F)|\geq 4\) and \(H\) is a forest with \(\Delta (H)\geq3\),
(c)
\(W^{-}_{F,H}(G)\leq 4\) if \(|V (F)|\geq 5\) and \(H\) is a forest with \(1\leq\Delta(H)\leq2\).
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.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory

References:

[1] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711-712. doi:; · Zbl 0331.05106
[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.; · Zbl 1367.05044
[3] D.W. Barnette, Trees in polyhedral graphs, Canad. J. Math. 18 (1966) 731-736. doi:; · Zbl 0141.21401
[4] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). doi:; · Zbl 1134.05001
[5] O.V. Borodin, A. Kostochka and M. Yancey, On 1-improper 2-coloring of sparse graphs, Discrete Math. 313 (2013) 2638-2649. doi:; · Zbl 1281.05060
[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:; · Zbl 1095.68075
[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:; · Zbl 1244.05088
[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:; · Zbl 1217.05087
[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:; · Zbl 1339.05116
[11] G. Chartrand, D.P. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Camb. Phil. Soc. 64 (1968) 265-271. doi:; · Zbl 0173.26204
[12] G. Chartrand, D.P. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Comb. Theory Ser. B 10 (1971) 12-41. doi:; · Zbl 0223.05101
[13] L. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited, J. Graph Theory 24 (1997) 205-219. doi:; · Zbl 0877.05019
[14] Z. Dvořák and D. Král’, On planar mixed hypergraphs, Electron. J. Combin. 8 (2001) R35.; · Zbl 1021.05032
[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:; · Zbl 1334.05030
[16] H.J. Fleischner, D.P. Geller and F. Harary, Outerplanar graphs and weak duals, J. Indian Math. Soc. 38 (1974) 215-219.; · Zbl 0352.05029
[17] T.-S. Fung, A colourful path, Math. Gaz. 73 (1989) 186-188. doi:; · Zbl 0677.05034
[18] M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comput. Sci. 1 (1976) 237-267. doi:; · Zbl 0338.05120
[19] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91-94. doi:; · Zbl 0742.05041
[20] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173.; · Zbl 1312.05050
[21] W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571-584. doi:; · Zbl 1317.05055
[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.; · Zbl 0984.05036
[24] A. Kündgen, E. Mendelsohn and V. Voloshin, Colouring planar mixed hypergraphs, Electron. J. Combin. 7 (2000) R60.; · Zbl 0978.05027
[25] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237-238.; · Zbl 0151.33401
[26] K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73-75. doi:; · Zbl 0705.05016
[27] B. Roy, Nombre chromatique et plus longs chemins d’un graphe, Rev. Franc. Inform. Rech. Op´er. 1 (1967) 129-132.; · Zbl 0157.31302
[28] Zs. Tuza, Graph colorings with local constraints-a survey, Discuss. Math. Graph Theory 17 (1997) 161-228. doi:; · Zbl 0923.05027
[29] V.I. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45-52.;
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.