EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Coloring Graphs With Forbidden Almost Bipartite Subgraphs

James Anderson, Anton Bernshteyn, Abhishek Dhawan

Random Structures & Algorithms · 2025-07 · 66 (4)

DOI: 10.1002/rsa.70012 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Random Structures & Algorithms, online erschienen am 16.06.2025. Verfasst von James Anderson und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 64 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Alon, Krivelevich, and Sudakov conjectured in 1999 that for every finite graph , there exists a quantity such that whenever is an ‐free graph of maximum degree . The largest class of connected graphs for which this conjecture has been verified so far, by Alon, Krivelevich, and Sudakov themselves, comprises the almost bipartite graphs (i.e., subgraphs of the complete tripartite graph for some ). However, the optimal value for remains unknown even for such graphs. Bollobás showed, using random regular graphs, that when contains a cycle. On the other hand, Davies, Kang, Pirot, and Sereni recently established an upper bound of . We improve this to a uniform constant, showing for every almost bipartite graph . This surprisingly makes the bound independent of in all the known cases of the conjecture. We also establish a more general version of our bound in the setting of DP‐coloring (also known as correspondence coloring) and consider some algorithmic consequences of our results.

Förderung

  • National Science Foundation

Zitieren

APA

Anderson, J., Bernshteyn, A., & Dhawan, A. (2025). Coloring Graphs With Forbidden Almost Bipartite Subgraphs. Random Structures & Algorithms, 66(4). https://doi.org/10.1002/rsa.70012

Vancouver

Anderson J, Bernshteyn A, Dhawan A. Coloring Graphs With Forbidden Almost Bipartite Subgraphs. Random Structures & Algorithms. 2025;66(4). doi:10.1002/rsa.70012

BibTeX
@article{Anderson2025,
  author = {Anderson, James and Bernshteyn, Anton and Dhawan, Abhishek},
  title = {Coloring Graphs With Forbidden Almost Bipartite Subgraphs},
  journal = {Random Structures & Algorithms},
  year = {2025},
  volume = {66},
  number = {4},
  doi = {10.1002/rsa.70012}
}
Kostenlos starten →