Improved bounds for some facially constrained colorings. (English) Zbl 1506.05078
In this paper, the author deals with families of graphs for three different and related chromatic problems in planar graphs.
First, 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. Some authors conjectured that 10 colors suffice in this coloring. In this paper, an infinite family of counterexamples that need 12 colors is presented. The best-known upper bound so far is 16 colors.
Second, 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. Some authors conjectured that 10 colors suffice in this coloring. In this paper, an infinite family of counterexamples that needs 12 colors is presented. The best-known upper bound so far is 97 colors.
Third, a facial \((P_k,P_l)\)-WORM coloring of a plane graph \(G\) is a vertex-coloring such that \(G\) contains neither a heterochromatic facial \(k\)-path nor a monochromatic facial \(l\)-path. Some authors proved that for any integer \(n\geq 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, and also asked whether there exists a graph with maximum degree \(4\) having the same property. In this paper, it is proved that for any integer \(n\geq 18\), there exists a connected plane graph, with maximum degree \(4\), with no facial \((P_3,P_3)\)-WORM coloring.
First, 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. Some authors conjectured that 10 colors suffice in this coloring. In this paper, an infinite family of counterexamples that need 12 colors is presented. The best-known upper bound so far is 16 colors.
Second, 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. Some authors conjectured that 10 colors suffice in this coloring. In this paper, an infinite family of counterexamples that needs 12 colors is presented. The best-known upper bound so far is 97 colors.
Third, a facial \((P_k,P_l)\)-WORM coloring of a plane graph \(G\) is a vertex-coloring such that \(G\) contains neither a heterochromatic facial \(k\)-path nor a monochromatic facial \(l\)-path. Some authors proved that for any integer \(n\geq 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, and also asked whether there exists a graph with maximum degree \(4\) having the same property. In this paper, it is proved that for any integer \(n\geq 18\), there exists a connected plane graph, with maximum degree \(4\), with no facial \((P_3,P_3)\)-WORM coloring.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Keywords:
plane graph; facial coloring; facial-parity edge-coloring; facial-parity vertex-coloring; WORM coloringReferences:
| [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.013 · Zbl 1244.05088 |
| [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.1502 · Zbl 1217.05087 |
| [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.008 · Zbl 1369.05067 |
| [4] | J. Czap, Parity vertex coloring of outerplane graphs, Discrete Math. 311 (2011) 2570-2573. doi:10.1016/j.disc.2011.06.009 · Zbl 1238.05088 |
| [5] | J. Czap, Facial parity edge coloring of outerplane graphs, Ars Math. Contemp. 5 (2012) 289-293. doi:10.26493/1855-3974.228.ee8 · Zbl 1258.05034 |
| [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.2319 · Zbl 1459.05056 |
| [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.026 · Zbl 1369.05071 |
| [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.be3 · Zbl 1237.05049 |
| [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.036 · Zbl 1245.05044 |
| [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.1921 · Zbl 1359.05037 |
| [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.008 · Zbl 1222.05051 |
| [12] | W. Goddard, K. Wash and H. Xu, WORM colorings forbidding cycles or cliques, Congr. Numer. 219 (2014) 161-173. · Zbl 1312.05050 |
| [13] | W. Goddard, K. Wash and H. Xu, WORM colorings, Discuss. Math. Graph Theory 35 (2015) 571-584. doi:10.7151/dmgt.1814 · Zbl 1317.05055 |
| [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. · Zbl 1288.05090 |
| [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.022 · Zbl 1281.05063 |
| [16] | Zs. Tuza, Graph colorings with local constraints[emdash.cyr]A survey, Discuss. Math. Graph Theory 17 (1997) 161-228. doi:10.7151/dmgt.1049 · Zbl 0923.05027 |
| [17] | V. Voloshin, The mixed hypergraphs, Comput. Sci. J. Moldova 1 (1993) 45-52. |
| [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.009 · Zbl 1248.05052 |
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.
