Concept

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 fewest colors needed in any acyclic coloring of G. Acyclic coloring is often associated with graphs embedded on non-plane surfaces. A(G) ≤ 2 if and only if G is acyclic. Bounds on A(G) in terms of Δ(G), the maximum degree of G, include the following: A(G) ≤ 4 if Δ(G) = 3. A(G) ≤ 5 if Δ(G) = 4. A(G) ≤ 7 if Δ(G) = 5. A(G) ≤ 12 if Δ(G) = 6. A milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum: Theorem A(G) ≤ 5 if G is planar graph. 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 induced forests. It is NP-complete to determine whether A(G) ≤ 3. showed that the decision variant of the problem is NP-complete even when G is a bipartite graph. demonstrated that every proper vertex coloring of a chordal graph is also an acyclic coloring. Since chordal graphs can be optimally colored in O(n + m) time, the same is also true for acyclic coloring on that class of graphs. A linear-time algorithm to acyclically color a graph of maximum degree ≤ 3 using 4 colors or fewer was given by .

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (3)
CS-250: Algorithms I
The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma
CH-450: Solid state chemistry and energy applications
You will learn about the bonding and structure of several important families of solid state materials. You will gain insight into common synthetic and characterization methods and learn about the appl
MATH-632: Semidefinite Optimization and Applications to Geometric and Combinatorial Problems
This course covers the following topics: Introduction to conic optimization, Duality in conic programming, Sums of squares/ SemideFinite relaxation for independence number and chromatic number, Harmon
Related publications (23)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.