EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Colouring graphs with forbidden bipartite subgraphs

James Anderson, Anton Bernshteyn, Abhishek Dhawan

Combinatorics, Probability and Computing · 2023-01 · 32 (1) · 45-67

DOI: 10.1017/s0963548322000104 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 08.06.2022. Verfasst von James Anderson und 2 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 25 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A conjecture of Alon, Krivelevich and Sudakov states that, for any graph $F$ , there is a constant $c_F \gt 0$ such that if $G$ is an $F$ -free graph of maximum degree $\Delta$ , then $\chi\!(G) \leqslant c_F \Delta/ \log\!\Delta$ . Alon, Krivelevich and Sudakov verified this conjecture for a class of graphs $F$ that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot and Sereni that if $G$ is $K_{t,t}$ -free, then $\chi\!(G) \leqslant (t + o(1)) \Delta/ \log\!\Delta$ as $\Delta \to \infty$ . We improve this bound to $(1+o(1)) \Delta/\log\!\Delta$ , making the constant factor independent of $t$ . We further extend our result to the DP-colouring setting (also known as correspondence colouring), introduced by Dvořák and Postle.

Zitieren

APA

Anderson, J., Bernshteyn, A., & Dhawan, A. (2023). Colouring graphs with forbidden bipartite subgraphs. Combinatorics, Probability and Computing, 32(1), 45-67. https://doi.org/10.1017/s0963548322000104

Vancouver

Anderson J, Bernshteyn A, Dhawan A. Colouring graphs with forbidden bipartite subgraphs. Combinatorics, Probability and Computing. 2023;32(1):45-67. doi:10.1017/s0963548322000104

BibTeX
@article{Anderson2023,
  author = {Anderson, James and Bernshteyn, Anton and Dhawan, Abhishek},
  title = {Colouring graphs with forbidden bipartite subgraphs},
  journal = {Combinatorics, Probability and Computing},
  year = {2023},
  volume = {32},
  number = {1},
  pages = {45--67},
  doi = {10.1017/s0963548322000104}
}
Kostenlos starten →