EUVIMEDEUVIMED entdecken
Crossref

Davies’s theorem and the coloring number of graphs

Péter Komjáth

Proceedings of the American Mathematical Society · 13.04.2026 · 154 (6) · 2659-2667

DOI: 10.1090/proc/16540 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the American Mathematical Society, online erschienen am 13.04.2026. Verfasst von Péter Komjáth. Die Arbeit nennt 14 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We generalize Davies’s famous example to a property of graphs: a graph ( V , X ) (V,X) is Davies if for every F : X → R F:X\to \mathbb {R} , there is a collection { g v : v ∈ V } \{g_v:v\in V\} of ω → R \omega \to \mathbb {R} functions such that F ( v , w ) = ∑ n > ω g v ( n ) g w ( n ) F(v,w)=\sum _{n>\omega } g_v(n)g_w(n) for { v , w } ∈ X \{v,w\}\in X . We show that if C o l ( X ) ≤ ω 1 \mathrm {Col}(X)\leq \omega _1 and | X | ≤ c |X|\leq \mathfrak {c} , then X X is Davies. On the other hand, there is a non-Davies graph X X with | X | = c + |X|=\mathfrak {c}^+ , C o l ( X ) = 3 \mathrm {Col}(X)=3 . If C h r ( X ) > c Chr(X)>\mathfrak {c} or C o l ( X ) > c + \mathrm {Col}(X)>\mathfrak {c}^+ , then X X is not Davies. If the existence of a supercompact cardinal is consistent, then so is that c = ℵ 3 \mathfrak {c}=\aleph _3 and any graph X X with C o l ( X ) > ω 1 \mathrm {Col}(X)>\omega _1 is not Davies.

Zitieren

APA

Komjáth, P. (2026). Davies’s theorem and the coloring number of graphs. Proceedings of the American Mathematical Society, 154(6), 2659-2667. https://doi.org/10.1090/proc/16540

Vancouver

Komjáth P. Davies’s theorem and the coloring number of graphs. Proceedings of the American Mathematical Society. 2026;154(6):2659-2667. doi:10.1090/proc/16540

BibTeX
@article{Komjth2026,
  author = {Komjáth, Péter},
  title = {Davies’s theorem and the coloring number of graphs},
  journal = {Proceedings of the American Mathematical Society},
  year = {2026},
  volume = {154},
  number = {6},
  pages = {2659--2667},
  doi = {10.1090/proc/16540}
}
Kostenlos starten →