Article in volume
Authors:
Title:
Improved bounds for some facially constrained colorings
PDFSource:
Discussiones Mathematicae Graph Theory 43(1) (2023) 151-158
Received: 2020-03-24 , Revised: 2020-07-30 , Accepted: 2020-07-30 , Available online: 2020-09-12 , https://doi.org/10.7151/dmgt.2357
Abstract:
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 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
vertex-coloring such that $G$ contains neither rainbow facial $k$-path nor
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 whether 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.
Keywords:
plane graph, facial coloring, facial-parity edge-coloring, facial-parity vertex-coloring, WORM coloring
References:
- Cs. Bujtás, E. Sampathkumar, Zs. Tuza, C. Dominic and L. Pushpalatha, Vertex coloring without large polychromatic stars, Discrete Math. 312 (2012) 2102–2108.
https://doi.org/10.1016/j.disc.2011.04.013 - Cs. Bujtás, E. Sampathkumar, Zs. Tuza, M. Subramanya and C. Dominic, $3$-consecutive c-colorings of graphs, Discuss. Math. Graph Theory 30 (2010) 393–405.
https://doi.org/10.7151/dmgt.1502 - Cs. Bujtás and Zs. Tuza, F-WORM colorings: Results for $2$-connected graphs, Discrete Appl. Math. 231 (2017) 131–138.
https://doi.org/10.1016/j.dam.2017.05.008 - J. Czap, Parity vertex coloring of outerplane graphs, Discrete Math. 311 (2011) 2570–2573.
https://doi.org/10.1016/j.disc.2011.06.009 - J. Czap, Facial parity edge coloring of outerplane graphs, Ars Math. Contemp. 5 (2012) 289–293.
https://doi.org/10.26493/1855-3974.228.ee8 - J. Czap, I. Fabrici and S. Jendroľ, Colorings of plane graphs without long monochromatic facial paths, Discuss. Math. Graph Theory 41 (2021) 801–808.
https://doi.org/10.7151/dmgt.2319 - J. Czap and S. Jendroľ, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703.
https://doi.org/10.1016/j.disc.2016.07.026 - J. Czap, S. Jendroľ and F. Kardoš, Facial parity edge colouring, Ars Math. Contemp. 4 (2011) 255–269.
https://doi.org/10.26493/1855-3974.129.be3 - J. Czap, S. Jendroľ, F. Kardoš and R. Soták, Facial parity edge colouring of plane pseudographs, Discrete Math. 312 (2012) 2735–2740.
https://doi.org/10.1016/j.disc.2012.03.036 - J. Czap, S. Jendroľ and J. Valiska, WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017) 353–368.
https://doi.org/10.7151/dmgt.1921 - J. Czap, S. Jendroľ and M. Voigt, Parity vertex colouring of plane graphs, Discrete Math. 311 (2011) 512–520.
https://doi.org/10.1016/j.disc.2010.12.008 - W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161–173.
- W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571–584.
https://doi.org/10.7151/dmgt.1814 - T. Kaiser, O. Rucký, M. Stehlík and R. Škrekovski, Strong parity vertex coloring of plane graphs, Discrete Math. Theor. Comput. Sci. 16 (2014) 143–158.
- B. Lužar and R. Škrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013) 2218–2222.
https://doi.org/10.1016/j.disc.2013.05.022 - Zs. Tuza, Graph colorings with local constraints–-A survey, Discuss. Math. Graph Theory 17 (1997) 161–228.
https://doi.org/10.7151/dmgt.1049 - V. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45–52.
- W. Wang, S. Finbow and P. Wang, An improved bound on parity vertex colourings of outerplane graphs, Discrete Math. 312 (2012) 2782–2787.
https://doi.org/10.1016/j.disc.2012.04.009
Close