Hypergraph extension of the Alon-Tarsi list coloring theorem (Q2387187): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import241208061232 (talk | contribs)
Normalize DOI.
 
(5 intermediate revisions by 4 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s00493-005-0020-8 / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: G. Wegner / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: G. Wegner / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1007/s00493-005-0020-8 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2128187567 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S00493-005-0020-8 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 08:20, 18 December 2024

scientific article
Language Label Description Also known as
English
Hypergraph extension of the Alon-Tarsi list coloring theorem
scientific article

    Statements

    Hypergraph extension of the Alon-Tarsi list coloring theorem (English)
    0 references
    0 references
    0 references
    26 January 2006
    0 references
    In a list coloring of a (hyper)graph the assignments of colors to the vertices have to be chosen from a list of colors associated to each vertex. A (hyper)graph is \(d\)-choosable if a coloring of the vertices avoiding monochromatic edges can be chosen from the lists whenever all lists have size at least \(d\). Alon-Tarsi's theorem says that a graph is \(d\)-choosable if it possesses an orientation such that the outdegree of every vertex is less than \(d\) and with the property that the number of circulations with an odd number of edges differs from the number of circulations with an even number edges. The aim of the paper is to generalize this result to \(k\)-uniform hypergraphs for prime \(k\). The proof makes use of the algebraic methods applied by Alon and Tarsi; for this purpose hypergraph polynomials are introduced.
    0 references
    list coloring
    0 references
    list chormatic number
    0 references
    \(k\)-choosable
    0 references
    hypergraph polynomials
    0 references
    combinatorial Nullstellensatz
    0 references
    0 references

    Identifiers