A relaxed Hadwiger's conjecture for list colorings (Q885300)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 5162683
Language Label Description Also known as
default for all languages
No label defined
    English
    A relaxed Hadwiger's conjecture for list colorings
    scientific article; zbMATH DE number 5162683

      Statements

      A relaxed Hadwiger's conjecture for list colorings (English)
      0 references
      0 references
      0 references
      8 June 2007
      0 references
      The authors prove the following result: For every positive integer \(k\), there exists a computable constant \(f(k)\) such that every finite and simple graph \(G\) without \(K_k\) as a minor admits a vertex partition \(V_1,\dots, V_{\lceil 15.5k\rceil}\) such that every component in the subgraph of \(G\) induced on \(V_i\) has at most \(f(k)\) vertices. This result is extended to list colorings and a conjecture is posed, too.
      0 references
      Hadwiger's conjecture
      0 references
      list coloring
      0 references

      Identifiers