Abstract
Let G be a simple and connected graph, and |V(G)| ≥ 2. A proper k -total-coloring of a graph G is a mapping f from V(G) ∪ E(G) into {1,2, ⋯ ,k} such that every two adjacent or incident elements of V(G) ∪ E(G) are assigned different colors. Let C(u) = f(u) ∪ {f(uv)|uv ∈ E(G)} be the neighbor color-set of u , if C(u) ≠ C(v) for any two vertices u and v of V(G), we say that f is a vertex-distinguishing proper k -total-coloring of G , or a k -VDT -coloring of G for short. The minimal number of all over k -VDT -colorings of G is denoted by χ vt (G), and it is called the VDTC chromatic number of G . In this paper, we obtain a new sequence of all combinations of 4 elements selected from the set {1,2, ⋯ ,n} by changing some combination positions appropriately on the lexicographical sequence, we call it the new triangle sequence. Using this technique, we obtain vertex distinguishing total chromatic number of ladder graphs.L m ≅ P m ×P 2 as follows: For ladder graphs L m and for any integer n = 9 + 8k(k = 1,2, ⋯ ). If \(\frac{(^{n-1}_{~4})}{2}+2 <m \leq \frac{(^{n}_{4})}{2}+2\), then χ vt (L m ) = n.
Supported by the NSFC of China (No.10771091) and Science Research Found of Ningxia University (No.(E)ndzr09-15).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Burris, A.C., Schelp, R.H.: Vertex-distinguishing Proper Edge-colorings. J. of Graph Theory 26(2), 3–82 (1997)
Bazgan, C., Harkat-Benhamdine, A., Li, H., Woźniak, M.: On the vertex-distinguishing proper edge-coloring of graph. J. of Combine. Theory, Ser. B 75, 288–301 (1999)
Balister, P.N., Riordan, O.M., Schelp, R.H.: Vertex-distinguishing coloring of graphs. J. of Graph Theory 42, 95–109 (2003)
Zhang, Z.F., Liu, L.Z., Wang, J.F.: Adjacent strong edge coloring of graphs. J. Applied Mathematics Letters 15, 623–626 (2002)
Hatami, H.: Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number. J. of Combinatorial Theory 95, 246–256 (2005)
Balister, P.N., Györi, E., Lehel, J., Schelp, P.H.: Adjacent vertex distinguishing edgecolorings. SIAM Journal On Discrete Mathematics 21, 237–250 (2006)
Zhang, Z.F., Li, J.W., Chen, X.E., et al.: D(β) Vertex-distinguishing proper edgecoloring of graphs. Acta Mathematica Sinica, Chinese Series 49(3), 703–708 (2006)
Akbari, S., Bidkhori, H., Nosrati, N.: r-Strong Edge Colorings of Graphs. Discrete Mathematics 306(23), 3005–3010 (2006)
Zhang, Z., Zhang, J., Wang, J.: The total chromatic number of some graphs. Sci. China Ser. A 31, 1434–1441 (1988)
Zhang, Z., Wang, J.: A summary of the progress on total colorings of graphs. Adv. in Math (China) 21, 90–397 (1992)
Zhang, Z., Chen, X., Li, J., et al.: On adjacent-vertex-distinguishing total coloring of graphs. Sci. China Ser. A 48(3), 289–299 (2005)
Wang, H.: On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ(G) = 3. Journal of Combinatorial Optimization 14(1), 87–109 (2007)
Chen, X.: On the adjacent vertex distinguishing total coloring numbers of graphs with Δ = 3. Discrete Mathematics 308, 4003–4007 (2008)
Hulgan, J.: Concise proofs for adjacent vertex-distinguishing total colorings. Discrete Mathematics 309(8), 2548–2550 (2009)
Wang, W., Wang, Y.: Adjacent vertex distinguishing total coloring of graphs with lower average degree. Taiwanese J. Math. 12, 979–990 (2008)
Wang, Y., Wang, W.: Adjacent vertex distinguishing total colorings of outerplanar graphs. Journal of Combinatorial Optimization (2008)
Zhang, Z., Qiu, P., Xu, B., et al.: Vertex-distinguishing total coloring of graphs. Ars Combinatoria. 87, 33–45 (2008)
Zhang, Z., Li, J., Chen, X., et al.: D(β)-vertex-distinguishing total colorings of graphs. Science in China Series A: Mathematics 48(10), 1430–1440 (2006) (in Chinese)
Zhang, Z., Cheng, H., Yao, B., et al.: On The adjacent-vertex-strongly-distinguishing total coloring of graphs. Science in China Series A: Mathematics 51(3), 427–436 (2008)
Zhang, Z., Qiu, P., Xu, B., et al.: Vertex distinguishing total coloring of graphs. Ars Combinatoria 87, 33–45 (2008)
Chartrand, G., Linda, L.F.: Graphs and Diagraphs, 2nd edn. Wadswirth Brooks/Cole, Monterey, CA (1986)
Hansen, P., Marcotte, O.: Graph coloring and application. AMS providence, Rhode Island USA (1999)
West, D.B.: Introduction to Graph Theory, 2nd edn. Person Education, Inc., Prentice Hall (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bao, S., Wang, Z., Wen, F. (2011). Vertex Distinguishing Total Coloring of Ladder Graphs. In: Qi, L. (eds) Information and Automation. ISIA 2010. Communications in Computer and Information Science, vol 86. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19853-3_17
Download citation
DOI: https://doi.org/10.1007/978-3-642-19853-3_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19852-6
Online ISBN: 978-3-642-19853-3
eBook Packages: Computer ScienceComputer Science (R0)