Separation choosability and dense bipartite induced subgraphs

Abstract

We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree $d$ contain a bipartite induced subgraph of minimum degree $\Omega (\log d)$ as $d\to \infty$?

18 pages; v2 accepted to Combinatorics, Probability & Computing

References in corpus (2)

• Colouring triangle-free graphs with local list sizes
• Dense induced bipartite subgraphs in triangle-free graphs

Cited by in corpus (7)

• Colouring triangle-free graphs with local list sizes
• On the power of random greedy algorithms
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Paintability of $r$-chromatic graphs
• A note on dense bipartite induced subgraphs
• A note on adaptable choosability and choosability with separation of planar graphs
• Single-conflict colouring