zbMATH — the first resource for mathematics

The adjacent vertex distinguishing total chromatic number. (English) Zbl 1245.05042
Summary: A well-studied concept is that of the total chromatic number. A proper total colouring of a graph is a colouring of both vertices and edges so that every pair of adjacent vertices receive different colours, every pair of adjacent edges receive different colours and every vertex and incident edge receive different colours. This paper considers a strengthening of this condition and examines the minimum number of colours required for a total colouring with the additional property that for any adjacent vertices \(u\) and \(v\), the set of colours incident to u is different from the set of colours incident to \(v\). It is shown that there is a constant \(C\) so that for any graph \(G\), there exists such a colouring using at most \(\Delta (G)+C\) colours.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI arXiv
[1] Aigner, M.; Triesch, E.; Tuza, Z., Irregular assignments and vertex-distinguishing edge-colorings of graphs, (), 1-9 · Zbl 0769.05035
[2] Balister, P.N.; Győri, E.; Lehel, J.; Schelp, R.H., Adjacent vertex distinguishing edge-colorings, SIAM J. discrete math., 21, 237-250, (2007) · Zbl 1189.05056
[3] M. Behzad, Graphs and their chromatic numbers, Diss., Michigan State University, 1965.
[4] Bollobás, B., Random graphs, (2001), Cambridge University Press Cambridge · Zbl 0997.05049
[5] Burris, A.C.; Schelp, R.H., Vertex-distinguishing proper edge-colorings, J. graph theory, 26, 73-82, (1997) · Zbl 0886.05068
[6] Černý, J.; Horňák, M.; Soták, R., Observability of a graph, Math. slovaca, 46, 21-31, (1996) · Zbl 0853.05040
[7] Chen, X., On the adjacent vertex distinguishing total coloring numbers of graphs with \(\Delta = 3\), Discrete math., 308, 4003-4007, (2008) · Zbl 1203.05052
[8] P. Erdős, L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, in: Infinite and Finite Sets, Colloq., Keszthely, vol. II, 1973, pp. 609-627.
[9] Hatami, H., \(\Delta + 300\) is a bound on the adjacent vertex distinguishing edge chromatic number, J. combin. theory ser. B, 95, 246-256, (2005) · Zbl 1075.05034
[10] Hulgan, J., Concise proofs for adjacent vertex-distinguishing total colorings, Discrete math., 309, 2548-2550, (2009) · Zbl 1221.05143
[11] J. Hulgan, Graph colorings with constraints, Diss. University of Memphis, 2010.
[12] Liu, X.S.; An, M.Q.; Gao, Y., An upper bound for the adjacent vertex-distinguishing total chromatic number of a graph, J. math. res. exposition, 29, 343-348, (2009) · Zbl 1212.05089
[13] McDiarmid, C.; Reed, B., Concentration for self-bounding functions and an inequality of talagrand, Random structures algorithms, 29, 549-557, (2006) · Zbl 1120.60015
[14] Molloy, M.; Reed, B., A bound on the total chromatic number, Combinatorica, 18, 241-280, (1998) · Zbl 0921.05033
[15] Talagrand, M., Concentration of measure and isoperimetric inequalities in product spaces, Publ. math. inst. hautes études sci., 81, 73-205, (1995) · Zbl 0864.60013
[16] Talagrand, M., New concentration inequalities in product spaces, Invent. math., 126, 505-563, (1996) · Zbl 0893.60001
[17] Vizing, V., Some unsolved problems in graph theory, Russian math. surveys, 23, 125-141, (1968) · Zbl 0192.60502
[18] Wang, H., On the adjacent vertex-distinguishing total chromatic numbers of the graphs with \(\Delta(G) = 3\), J. comb. optim., 14, 87-109, (2007) · Zbl 1125.05043
[19] Zhang, Z.; Chen, X.; Li, J.; Yao, B.; Lu, X.; Wang, J., On adjacent-vertex-distinguishing total coloring of graphs, Sci. China ser. A, 48, 289-299, (2005) · Zbl 1080.05036
[20] Zhang, Z.; Liu, L.; Wang, J., Adjacent strong edge coloring of graphs, Appl. math. lett., 15, 623-626, (2002) · Zbl 1008.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.