关键词: 扇形图, 外平面图, 弱完备染色, 弱完备色数, 最大度

Abstract:

Let G=(V, E, F) be a plane graph. If e₁ and e₂ are consecutively adjacent with the same face, then we say that e₁ and e₂ are facially adjacent. A plane graph G is called weakly entire k-colorable if there is a mapping from V ∪ E ∪ F to {1, …, K} such that any facially adjacent edges, adjacent vertices, adjacent faces, and any two incident elements in V ∪ E ∪ F receive distinct colors. The weakly entire chromatic number, denoted χ_vef(G), of G is defined to be the least integer k such that G is weakly entire k-colorable. In 2016, Fabrici et al. conjectured that every connected, loopless, bridgeless plane graph is weakly entire 7-colorable. In this paper, we prove that the conjecture is true for outerplanar graphs. Namely, outerplanar graphs are weakly entire 7-colorable.

Key words: fan graph, outerplanar graph, weakly entire coloring, weakly entire chromatic number, maximum degree