Added to Favorites

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors.## References

Example 1. A minimal imperfect graph is a graph in which every subgraph is perfect. The deletion of any vertex from a minimal imperfect graph leaves a uniquely colorable subgraph.

Some properties of a uniquely k-colorable graph G with n vertices and m edges:

- m ≥ (k - 1) n - k(k-1)/2. (Truszczyński 1981; Xu 1990)

A uniquely edge-colorable graph is a k-edge-chromatic graph that has only one possible (proper) k-edge-coloring up to permutation of the colors.

Example 2. The stars K_{1,k} are uniquely k-edge-colorable graphs. Moreover, R. J. Wilson (1967) conjectured and A. G. Thomason (1978) proved that, when k ≥ 4, they are also the only members in this family.
See [Bollobás 1978].

A uniquely total colorable graph is a k-total-chromatic graph that has only one possible (proper) k-total-coloring up to permutation of the colors.

Example 3. Empty graphs, paths, and cycles of length divisible by 3 are uniquely total colorable graphs. Mahmoodian and Shokrollahi (1995) conjectured that they are also the only members in this family.

Some properties of a uniquely k-total-colorable graph G with n vertices:

- χ″(G) = Δ(G) + 1 unless G = K
_{2}. (Akbari et al. 1997) - Δ(G) ≤ 2 δ(G). (Akbari et al. 1997)
- Δ(G) ≤ n/2 + 1. (Akbari 2003)

Here χ″(G) is the total chromatic number; Δ(G), maximum degree; and δ(G), minimum degree.

- Akbari, S. (2003). Two conjectures on uniquely totally colorable graphs. Discrete Math. 266(1-3), 41–45.
- Akbari, S.; Behzad, M.; Haijiabolhassen, H.; Mahmoodian (1997). Uniquely total colorable graphs. Graphs Combin. 13, 305–314.
- Bollobás, Béla (1978). Extremal graph theory, Vol. 11, LMS Monographs. London; New York; San Francisco: Academic Press.
- Hillar, C.; Windfeldt, T., An algebraic characterization of uniquely vertex colorable graphs, Journal of Combinatorial Theory Series B, 98 (2008), 400–414.
- Mahmoodian, E. S.; Shokrollahi, M. A. (1995). Open problems at the combinatorics workshop of AIMC25 (Tehran, 1994), in Combinatorics Advances. In Colbourn, C. J.; Mahmoodian, E. S. (Eds.), Mathematics and its applications, 321–324. Dordrecht; Boston; London: Kluwer Academic Publishers.
- Truszczyński, M. (1981). Some results on uniquely colourable graphs. Soloquia Math. Soc. János Bolyai, 37, 733–746.
- Xu, Shaoji (1990). The size of uniquely colorable graphs. J. Combin. Theory (B) 50, 319–320.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday May 04, 2008 at 15:59:23 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday May 04, 2008 at 15:59:23 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.