Separation choosability and dense bipartite induced subgraphs

DOI10.1017/S0963548319000026MaRDI QIDQ5222550zbMATH OpenOpenAlexWikidataFDO

Authors L. Esperet, Ross J. Kang, Stéphan Thomassé

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1802.03727

zbMATH Keywords

list coloringvertex coloringchoice numbers

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

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(logd)$ as $doinfty$?

Recommendations

• Bipartite induced density in triangle-free graphs
• On choosability with separation of planar graphs with forbidden cycles
• Choosability with union separation of triangle-free planar graphs
• On choosability with separation of planar graphs with lists of different sizes
• Choosability with separation of complete multipartite graphs and hypergraphs

Cites work

• scientific article; zbMATH DE number 4213473 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 1496580 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A class of three-colorable triangle-free graphs
• A dense infinite Sidon sequence
• A note on Ramsey numbers
• Adapted List Coloring of Graphs and Hypergraphs
• Bipartite induced density in triangle-free graphs
• Brooks-type theorems for choosability with separation
• Choosability with separation of complete multipartite graphs and hypergraphs
• Coloring triangle-free graphs with local list sizes
• Coloring, sparseness and girth
• Complexity of choosing subsets from color sets
• Dense induced bipartite subgraphs in triangle-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• Hypergraph containers
• On colouring random graphs
• On the independence number of sparse graphs
• The adaptable choosability number grows with the choosability number
• The choice number of random bipartite graphs
• The chromatic number of random graphs
• The chromatic number of random graphs
• The early evolution of the \(H\)-free process
• The list chromatic number of graphs with small clique number
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(10)

• List 4-colouring of planar graphs
• Dense induced bipartite subgraphs in triangle-free graphs
• Dense Induced Subgraphs of Dense Bipartite Graphs
• Minimal abundant packings and choosability with separation
• On the power of random greedy algorithms
• Counterexamples to a Conjecture of Harris on Hall Ratio
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Some results on chromatic number as a function of triangle count
• Bipartite induced density in triangle-free graphs
• Single‐conflict colouring

This page was built for publication: Separation choosability and dense bipartite induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222550)