
arXiv: 2005.09979
A facial-parity edge-coloring of a $2$-edge-connected plane graph is a facially-proper edge-coloring in which every face is incident with zero or an odd number of edges of each color. A facial-parity vertex-coloring of a $2$-connected plane graph is a facially-proper vertex-coloring in which every face is incident with zero or an odd number of vertices of each color. Czap and Jendroľ (in Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017), 2691--2703), conjectured that $10$ colors suffice in both colorings. We present an infinite family of counterexamples to both conjectures. A facial $(P_{k}, P_{\ell})$-WORM coloring of a plane graph $G$ is a coloring of the vertices such that $G$ contains no rainbow facial $k$-path and no monochromatic facial $\ell$-path. Czap, Jendroľ and Valiska (in WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017), 353--368), proved that for any integer $n\ge 12$ there exists a connected plane graph on $n$ vertices, with maximum degree at least $6$, having no facial $(P_{3},P_{3})$-WORM coloring. They also asked if there exists a graph with maximum degree $4$ having the same property. We prove that for any integer $n\ge 18$, there exists a connected plane graph, with maximum degree $4$, with no facial $(P_{3},P_{3})$-WORM coloring.
FOS: Computer and information sciences, plane graph, WORM coloring, facial-parity edge-coloring, Discrete Mathematics (cs.DM), 05C15, 05C10, facial coloring, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, 05c15, QA1-939, FOS: Mathematics, 05c10, Mathematics - Combinatorics, Combinatorics (math.CO), facial-parity vertex-coloring, Mathematics, worm coloring, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, plane graph, WORM coloring, facial-parity edge-coloring, Discrete Mathematics (cs.DM), 05C15, 05C10, facial coloring, Planar graphs; geometric and topological aspects of graph theory, Coloring of graphs and hypergraphs, 05c15, QA1-939, FOS: Mathematics, 05c10, Mathematics - Combinatorics, Combinatorics (math.CO), facial-parity vertex-coloring, Mathematics, worm coloring, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
