Separation choosability and dense bipartite induced subgraphs

DOI10.1017/S0963548319000026zbMATH Open1436.05036arXiv1802.03727OpenAlexW2786734235WikidataQ128322250 ScholiaQ128322250MaRDI QIDQ5222550FDOQ5222550

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)

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$?

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

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

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)

Cites Work

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

Cited In (10)

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

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)