Acyclic coloring

Acyclic coloring

In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic.The acyclic chromatic number A("G") of a graph "G" is the least number of colors needed in any acyclic coloring of "G".

Some properties of A("G"):
# A("G") ≤ 2 if and only if "G" is acyclic.
# A("G") ≤ 4 if Δ("G") = 3, where Δ("G") is the maximum degree of "G". (Grünbaum 1973)
# A("G") ≤ 5 if Δ("G") = 4. (Burstein 1979)
# It is NP-complete to determine whether A("G") ≤ 3. (Kostochka 1978)

A milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum:

Theorem. (Borodin 1979) :A("G") ≤ 5 if "G" is planar graph.

Grünbaum (1973) introduced acyclic coloring and acyclic chromatic number, and conjectured the result in the above theorem.Borodin's proof involved several years of painstaking inspection of 450 reducible configurations.One consequence of this theorem is that every planar graph can be decomposed into an independent set and two forests. (Stein 1970, 1971)

Acyclic coloring is often associated with graphs embedded on non-plane surfaces.

References

* Borodin, O. V. (1979). On acyclic colorings of planar graphs. "Discrete Math." 25, 211–236.
* Burstein, M. I. (1979). Every 4-valent graph has an acyclic 5-coloring (in Russian). "Soobšč. Akad. Nauk Gruzin. SSR" 93, 21–24.
* Grünbaum, B. (1973). Acyclic colorings of planar graphs. "Israel J. Math." 14, 390–408.
* Jensen, Tommy R.; Toft, Bjarne (1995). "Graph coloring problems". New York: Wiley-Interscience. ISBN 0-471-02865-7.
* Kostochka, A. V. (1978). "Upper bounds of chromatic functions of graphs" (in Russian). Doctoral thesis, Novosibirsk.
* Stein, S. K. (1970). B-sets and coloring problems. "Bull. Amer. Math. Soc." 76, 805–806.
* Stein, S. K. (1971). B-sets and planar maps. "Pacific J. Math." 37(1), 217–224.


Wikimedia Foundation. 2010.

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

Look at other dictionaries:

  • 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

  • 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 (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A …   Wikipedia

  • Degeneracy (graph theory) — In graph theory, a k degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph s edges. The degeneracy of a graph is the smallest… …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • Список терминов, относящихся к алгоритмам и структурам данных —   Это служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавливается на информационные списки и глоссарии …   Википедия

  • Список терминов — Список терминов, относящихся к алгоритмам и структурам данных   Это сл …   Википедия

  • Mihalis Yannakakis — Born September 13, 1953 …   Wikipedia

Share the article and excerpts

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