Coloring Graphs With Forbidden Almost Bipartite Subgraphs
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.
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}
}
EUVIMED