Planar graphs with $$\Delta =9$$ are neighbor-distinguishing totally 12-colorable
Tóm tắt
The neighbor-distinguishing total coloring of a graph G is a proper total coloring of G using k colors such that any two adjacent vertices have different sets of colors. It was known that every planar graph G with $$\Delta \ge 10$$ is neighbor-distinguishing totally $$(\Delta +3)$$-colorable. In this paper, we extend this result to the case $$\Delta =9$$. Namely, we prove that every planar graph G with $$\Delta =9$$ is neighbor-distinguishing totally 12-colorable.
Tài liệu tham khảo
Alon N (1999) Combinatorial nullstellensatz. Comb Probab Comput 8:7–29
Appel K, Haken W (1976) Every planar map is four colourable. Bull Am Math Soc 82:711–712
Chen X (2008) On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta =3\). Discrete Math 308:4003–4007
Cheng X, Wang G, Wu J (2017) The adjacent vertex distinguishing total chromatic numbers of planar graphs with \(\Delta =10\). J Comb Optim 34:383–397
Coker T, Johannson K (2012) The adjacent vertex distinguishing total chromatic number. Discrete Math 312:2741–2750
Grötzsch H (1959) Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss Z Martin Luther-Univ Halle Wittenberg, Math-Nat Reihe 8:109–120
Huang D, Wang W, Yan C (2012) A note on the adjacent vertex distinguishing total chromatic number of graphs. Discrete Math 312:3544–3546
Huang D, Wang W (2012) Adjacent vertex distinguishing total colorings of planar graphs with large maximum degree. Sci Sin Math 42:151–164
Hulgan J (2009) Concise proofs for adjacent vertex-distinguishing total colorings. Discrete Math 309:2548–2550
Lu Y, Li J, Luo R, Miao Z (2017) Adjacent vertex distinguishing total coloring of graphs with maximum degree 4. Discrete Math 340:119–123
Sanders D, Zhao Y (2001) Planar graphs of maximum degree seven are Class I. J Comb Theory Ser B 83:201–212
Vizing VG (1964) On an estimate of the chromatic index of a p-graph. Diskret Anal 3:25–30
Wang H (2007) On the adjacent vertex distinguishing total chromatic number of the graphs with \(\Delta (G)=3\). J Comb Optim 14:87–109
Wang W, Wang Y (2008) Adjacent vertex distinguishing total coloring of graphs with lower average degree. Taiwanese J Math 12:979–990
Wang W, Wang P (2009) On adjacent-vertex-distinguishing total coloring of \(K_{4}\)-minor free graphs. Sci China Ser A 39:1462–1472
Wang W, Huang D (2014) The adjacent vertex distinguishing total coloring of planar graphs. J Comb Optim 27:379–396
Wang Y, Wang W (2010) Adjacent vertex distinguishing total colorings of outerplanar graphs. J Comb Optim 19:123–133
Zhang Z, Chen X, Li J, Yao B, Lu X, Wang J (2005) On adjacent-vertex-distinguishing total coloring of graphs. Sci China Ser A 48:289–299