1. bookAHEAD OF PRINT
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
access type Accès libre

Improved Bounds for Some Facially Constrained Colorings

Publié en ligne: 29 Sep 2020
Volume & Edition: AHEAD OF PRINT
Pages: -
Reçu: 24 Mar 2020
Accepté: 30 Jul 2020
Détails du magazine
License
Format
Magazine
eISSN
2083-5892
Première parution
13 Apr 2013
Périodicité
4 fois par an
Langues
Anglais
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 (Pk, Pl)-WORM coloring of a plane graph G is a vertex-coloring such that G contains neither rainbow facial k-path nor monochromatic facial l-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 ≥ 12 there exists a connected plane graph on n vertices, with maximum degree at least 6, having no facial (P3, P3)-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 ≥ 18, there exists a connected plane graph, with maximum degree 4, with no facial (P3, P3)-WORM coloring.

Keywords

MSC 2010

[1] 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.01310.1016/j.disc.2011.04.013Search in Google Scholar

[2] 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. doi:10.7151/dmgt.150210.7151/dmgt.1502Search in Google Scholar

[3] Cs. Bujtás and Zs. Tuza, F-WORM colorings: Results for 2-connected graphs, Discrete Appl. Math. 231 (2017) 131–138. doi:10.1016/j.dam.2017.05.00810.1016/j.dam.2017.05.008Search in Google Scholar

[4] J. Czap, Parity vertex coloring of outerplane graphs, Discrete Math. 311 (2011) 2570–2573. doi:10.1016/j.disc.2011.06.00910.1016/j.disc.2011.06.009Search in Google Scholar

[5] J. Czap, Facial parity edge coloring of outerplane graphs, Ars Math. Contemp. 5 (2012) 289–293. doi:10.26493/1855-3974.228.ee810.26493/1855-3974.228.ee8Search in Google Scholar

[6] J. Czap, I. Fabrici and S. Jendroľ, Colorings of plane graphs without long monochromatic facial paths, Discuss. Math. Graph Theory, in press. doi:10.7151/dmgt.231910.7151/dmgt.2319Search in Google Scholar

[7] J. Czap and S. Jendroľ, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2703. doi:10.1016/j.disc.2016.07.02610.1016/j.disc.2016.07.026Search in Google Scholar

[8] J. Czap, S. Jendroľ and F. Kardoš, Facial parity edge colouring, Ars Math. Contemp. 4 (2011) 255–269. doi:10.26493/1855-3974.129.be310.26493/1855-3974.129.be3Search in Google Scholar

[9] J. Czap, S. Jendroľ, F. Kardoš and R. Soták, Facial parity edge colouring of plane pseudographs, Discrete Math. 312 (2012) 2735–2740. doi:10.1016/j.disc.2012.03.03610.1016/j.disc.2012.03.036Search in Google Scholar

[10] J. Czap, S. Jendroľ and J. Valiska, WORM colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017) 353–368. doi:10.7151/dmgt.192110.7151/dmgt.1921Search in Google Scholar

[11] J. Czap, S. Jendroľ and M. Voigt, Parity vertex colouring of plane graphs, Discrete Math. 311 (2011) 512–520. doi:10.1016/j.disc.2010.12.00810.1016/j.disc.2010.12.008Search in Google Scholar

[12] W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161–173.Search in Google Scholar

[13] W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571–584. doi:10.7151/dmgt.181410.7151/dmgt.1814Search in Google Scholar

[14] 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.Search in Google Scholar

[15] B. Lužar and R. Škrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013) 2218–2222. doi:10.1016/j.disc.2013.05.02210.1016/j.disc.2013.05.022Search in Google Scholar

[16] Zs. Tuza, Graph colorings with local constraints[emdash.cyr]A survey, Discuss. Math. Graph Theory 17 (1997) 161–228. doi:10.7151/dmgt.104910.7151/dmgt.1049Search in Google Scholar

[17] V. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45–52.Search in Google Scholar

[18] W. Wang, S. Finbow and P. Wang, An improved bound on parity vertex colourings of outerplane graphs, Discrete Math. 312 (2012) 2782–2787. doi:10.1016/j.disc.2012.04.00910.1016/j.disc.2012.04.009Search in Google Scholar

Articles recommandés par Trend MD

Planifiez votre conférence à distance avec Sciendo