Choosability with separation of complete multipartite graphs and hypergraphs
From MaRDI portal
Abstract: For a hypergraph G and a positive integer s, let chi_{ell} (G,s) be the minimum value of l such that G is L-colorable from every list L with |L(v)|=l for each vin V(G) and |L(u)cap L(v)|leq s for all u, vin ein E(G). This parameter was studied by Kratochv'{i}l, Tuza and Voigt for various kinds of graphs. Using randomized constructions we find the asymptotics of chi_{ell} (G,s) for balanced complete multipartite graphs and for complete k-partite k-uniform hypergraphs.
Recommendations
- The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
- Choosability in random hypergraphs
- Vertex coloring complete multipartite graphs from random lists of size 2
- On the asymptotic value of the choice number of complete multi‐partite graphs
- On the Choice Numbers of Some Complete Multipartite Graphs
Cites work
- Brooks-type theorems for choosability with separation
- Choice Numbers of Graphs: a Probabilistic Approach
- On a combinatorial problem. II
- On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs
- On the asymptotic value of the choice number of complete multi‐partite graphs
- On the ratio of optimal integral and fractional covers
Cited in
(16)- A sufficient condition for planar graphs to be (3,1)-choosable
- Choosability with union separation
- The list-chromatic number of complete multipartite hypergraphs and multiple covers by independent sets
- Choosability with separation of planar graphs without prescribed cycles
- On choosability with separation of planar graphs with lists of different sizes
- On choosability of some complete multipartite graphs and Ohba's conjecture
- On choosability with separation of planar graphs with forbidden cycles
- Coloring, sparseness and girth
- On-line choice number of complete multipartite graphs: an algorithmic approach
- Separation choosability and dense bipartite induced subgraphs
- Single‐conflict colouring
- List 4-colouring of planar graphs
- Minimal abundant packings and choosability with separation
- On list coloring with separation of the complete graph and set system intersections
- Choosability with separation of cycles and outerplanar graphs
- On choosability with separation of planar graphs without adjacent short cycles
This page was built for publication: Choosability with separation of complete multipartite graphs and hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5418773)
