A note on vertex colorings of plane graphs

Fabrici, Igor; Jendrol', Stanislav GND; Harant, Jochen GND; Soták, Roman

Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) 6= c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.

Cite

Citation style:
Fabrici, I., Jendrol’, S., Harant, J., Soták, R., 2014. A note on vertex colorings of plane graphs. Discussiones mathematicae 34, 2014, 849–855. https://doi.org/10.7151/dmgt.1771
Could not load citation form. Default citation form is displayed.

Rights

Use and reproduction:

Export