@article{20422,
  abstract     = {We show that if n is odd and p>=Clog n/n, then with high probability Hamilton cycles in G(n,p) span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with odd n vertices and minimum degree n/2+C for sufficiently large constant C, span its cycle space.
},
  author       = {Christoph, Micha and Nenadov, Rajko and Petrova, Kalina H},
  issn         = {1096-0902},
  journal      = {Journal of Combinatorial Theory Series B},
  pages        = {254--267},
  publisher    = {Elsevier},
  title        = {{The Hamilton space of pseudorandom graphs}},
  doi          = {10.1016/j.jctb.2025.09.002},
  volume       = {176},
  year         = {2026},
}

@article{9602,
  abstract     = {An ordered graph is a graph with a linear ordering on its vertex set. We prove that for every positive integer k, there exists a constant ck > 0 such that any ordered graph G on n vertices with the property that neither G nor its complement contains an induced monotone path of size k, has either a clique or an independent set of size at least n^ck . This strengthens a result of Bousquet, Lagoutte, and Thomassé, who proved the analogous result for unordered graphs.
A key idea of the above paper was to show that any unordered graph on n vertices that does not contain an induced path of size k, and whose maximum degree is at most c(k)n for some small c(k) > 0, contains two disjoint linear size subsets with no edge between them. This approach fails for ordered graphs, because the analogous statement is false for k ≥ 3, by a construction of Fox. We provide some further examples showing that this statement also fails for ordered graphs avoiding other ordered trees.},
  author       = {Pach, János and Tomon, István},
  issn         = {0095-8956},
  journal      = {Journal of Combinatorial Theory. Series B},
  pages        = {21--37},
  publisher    = {Elsevier},
  title        = {{Erdős-Hajnal-type results for monotone paths}},
  doi          = {10.1016/j.jctb.2021.05.004},
  volume       = {151},
  year         = {2021},
}

@article{22156,
  abstract     = {Extending a recent breakthrough of Shitov, we prove that the chromatic number of the tensor product of two graphs can be a constant factor smaller than the minimum chromatic number of the two graphs. More precisely, we prove that there exists an absolute constant δ>0 such that for all c sufficiently large, there exist graphs G and H with chromatic number at least (1+δ)c for which χ(G×H)≤c.},
  author       = {He, Xiaoyu and Wigderson, Yuval},
  issn         = {0095-8956},
  journal      = {Journal of Combinatorial Theory, Series B},
  keywords     = {Graph coloring, Hedetniemi's conjecture},
  pages        = {485--494},
  publisher    = {Elsevier},
  title        = {{Hedetniemi's conjecture is asymptotically false}},
  doi          = {10.1016/j.jctb.2020.03.003},
  volume       = {146},
  year         = {2021},
}