Uniquely colorable graph

Uniquely colorable graph

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.

"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.

References

* 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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • List of mathematics articles (U) — NOTOC U U duality U quadratic distribution U statistic UCT Mathematics Competition Ugly duckling theorem Ulam numbers Ulam spiral Ultraconnected space Ultrafilter Ultrafinitism Ultrahyperbolic wave equation Ultralimit Ultrametric space… …   Wikipedia

  • Edge coloring — A 3 edge coloring of the Desargues graph. In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”