Abstract
Uniquely vertex colorable graphs and uniquely edge colorable graphs have been studied extensively by different authors. The literature on the similar problem for total coloring is void. In this paper we study this concept and, among other results, we prove that if a graph G ≠ K 2 is uniquely total colorable, then χ″(G) = Δ + 1. Our results support the following conjecture: empty graphs, paths, and cycles of order 3k, k a natural number, are the only uniquely total colorable graphs.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Behzad, M.: Graphs and their chromatic numbers. PhD dissertation, Michigan State University, Department of Mathematics, 1965
—, Some problems in total graph theory, in Combinatorics Advances. In: C.J. Colbourn and E.S. Mahmoodian, eds., Mathematics and Its Applications pp. 13–26 Dordrecht, Boston, London: Kluwer Academic 1995
Behzad, M., Chartrand, G.: An introduction to total graphs, in Theory of Graphs. Inter. Symposium, Rome, July 1966, P. Rosenstiehl, ed., New York, 1967, Gordon and Breach, pp. 31–33
Behzad, M., Chartrand, G., Lesniak-Foster, L.: Graphs and Digraphs, Prindle. Boston: Weber, and Schmidt 1979
Bollobás, B.: Extremal Graph Theory, vol. 11 of LMS Monographs. London, New York, San Francisco: Academic Press 1978
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. New York: American Elsevier 1976
Chartrand, G., Geller, D.: On uniquely colorable planar graphs. J. Comb. Theory 6, 271–278 (1969)
Fiorini, S.: On the chromatic index of a graph, III: Uniquely edge-colourable graphs. Quart. J. Math. Oxford 26, 129–140 (1975)
Hall, M.: Distinct representatives of subsets. Bull. Amer. Math. Soc. 54, 922–926 (1948)
Greenwell, D.L., Kronk, H.V.: Uniquely line colorable graphs. Canad. Math. Bull. 16, 525–529 (1973)
Mahmoodian, E.S., Rostamaabadi, F.: Uniquely total colorable graph conjecture is true for all graphs with less than 11 vertices. Tech. Rep. 1, Sharif University of Technology, Department of Mathematical Sciences, Tehran, Iran, April 1995
Mahmoodian, E.S., Shokrollahi, M.A.: Open problems at the combinatorics workshop of AIMC25 (Tehran, 1994). In Combinatorics Advances. C.J. Colbourn and E.S. Mahmoodian, eds., Mathematics and Its Applications pp. 321–324 Dordrecht, Boston, London: Kluwer Academic 1995
Shaoji, X.: On the size of uniquely colorable graphs, J. Comb. Theory Ser. B 50, 319–320 (1990)
Truszczyński, M.: Some results on uniquely colourable graphs. Colloquia Math. Soc. János Bolyai 37, 733–746 (1981)
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of third and fourth author was partially supported by the Institute for Studies in Theoretical Physics and Mathematics (IPM), Tehran, Iran
Rights and permissions
About this article
Cite this article
Akbari, S., Behzad, M., Hajiabolhassan, H. et al. Uniquely Total Colorable Graphs. Graphs and Combinatorics 13, 305–314 (1997). https://doi.org/10.1007/BF03353009
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF03353009