Acyclic edge coloring of sparse graphs (Q1759399): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.disc.2012.08.012 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1978597841 / rank
 
Normal rank

Revision as of 21:15, 19 March 2024

scientific article
Language Label Description Also known as
English
Acyclic edge coloring of sparse graphs
scientific article

    Statements

    Acyclic edge coloring of sparse graphs (English)
    0 references
    0 references
    0 references
    20 November 2012
    0 references
    An acyclic edge coloring of a graph \(G\) is a proper edge coloring that results in no bichromatic cycle. A graph \(G\) ist called acyclically edge \(k\)-colorable if it admits an acyclic edge coloring using at most \(k\) colours. The acyclic chromatic index of a graph \(G\) is the minimum number \(k\) such that \(G\) is acyclically edge \(k\)-colorable. In 1978 it was conjectured that every graph is acyclically edge \((\Delta+2)\)-colorable. In the present paper the conjecture is proved for graphs with maximum average degree less than 4. As a corollary, triangle-free planar graphs prove to be edge \((\Delta+2)\)-colorable.
    0 references
    acyclic edge coloring
    0 references
    acyclic chromatic index
    0 references

    Identifiers