List-coloring clique-hypergraphs of K5-minor-free graphs strongly

Abstract Let G be a connected simple graph with at least one edge. The hypergraph H = H ( G ) with the same vertex set as G whose hyper-edges are the maximal cliques of G is called the clique-hypergraph of G . A list-assignment of G is a function L which assigns to each vertex v ∈ V ( G ) a set L ( v ) (called the list of v ). A k -list-assignment of G is a list-assignment L such that L ( v ) has at least k elements for every v ∈ V ( G ) . For a given list assignment L , a list-coloring of H ( G ) is a function c : V ( G ) → ∪ v L ( v ) such that c ( v ) ∈ L ( v ) for every v ∈ V ( G ) and no hyper-edge of H ( G ) is monochromatic. A list-coloring of H ( G ) is strong if no 3-cycle of G is monochromatic. H ( G ) is (strongly) k -choosable if, for every k -list assignment L , there exists a (strong) list-coloring of H ( G ) . Mohar and S ˇ krekovski proved that the clique-hypergraphs of planar graphs are strongly 4-choosable (Electr. J. Combin. 6 (1999), #R26). In this paper we give a short proof of the result and present a linear time algorithm for the strong list-4-coloring of H ( G ) if G is a planar graph. In addition, we prove that H ( G ) is strongly 4-choosable if G is a K 5 -minor-free graph, which is a generalization of their result.