中文

Operations Research Transactions >

2021 , Vol. 25 >Issue 1: 132 - 136

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2021.01.013

Weakly entire coloring of outerplanar graphs

Expand
  • 1. Department of Mathematics, Zhejiang NormalUniversity, Jinhua 321004, Zhejiang, China

Received date: 2019-09-06

  Online published: 2021-03-05

Fold

Abstract

Let G=(V, E, F) be a plane graph. If e1 and e2 are consecutively adjacent with the same face, then we say that e1 and e2 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

Cite this article

Min CHEN, Jianmin YANG, Hao ZHANG, Yiting WANG . Weakly entire coloring of outerplanar graphs[J]. Operations Research Transactions, 2021 , 25(1) : 132 -136 . DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.013

References

1 Kronk H , Mitchem J . A seven-color theorem on the sphere[J]. Discrete Mathematics, 1973, 5 (1): 253- 260.
2 Borodin O V . On the total coloring of planar graphs[J]. Journal für die reine und angewandte Mathematik, 1989, 394 (1): 180- 185.
3 Borodin O V . Structural theorem on plane graphs with application tothe entire coloring number[J]. Journal of Graph Theory, 1996, 23 (3): 233- 239.
4 Sanders D P , Zhao Y . On the entire coloring conjecture[J]. Canadian Mathematical Bulletin, 2000, 43 (1): 108- 114.
5 Wang W , Zhu X . Entire colouring of plane graphs[J]. Journal of Combinatorial Theory Series B, 2011, 101 (6): 490- 501.
6 Fabrici I , Jendrol S , Vrbjarova M . Facial entire colouring of planegraphs[J]. Discrete Mathematics, 2016, 339 (2): 626- 631.
7 Chen M , Fan Y , Wang Y , et al. A sufficient condition for planargraphs to be (3, 1)-choosable[J]. Journal of Combinatorial Optimization, 2017, 34 (4): 987- 1011.
8 Chen M , Raspaud A , Wang W . Plane graphs with maximum degree 6 areedge-face 8-colorable[J]. Graphs & Combinatorics, 2014, 30 (4): 861- 874.
9 Cai J S , Wang J H , Zhang X . Restricted Colorings of Graphs[M]. Beijing: Science Press, 2019.
10 Bondy J. Murty U. Graph Theory[M]. New York: Springer, 2008.
11 Wang W F . On complete colouring of outerplanar graph[J]. Journal ofLiaoning University, 1992, 19 (1): 16- 21.
12 Wang W F . Edge-face entire chromatic number of outerplanar graphs[J]. Journal of Liaoning University, 1994, 21 (4): 1- 9.
Options
Outlines

/

〈 〉