An official website of the United States government
Abstract 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.
more »
« less
Equitable colourings of Borel graphs
Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $$\Delta $$ , then for every integer $$k \geq \Delta +1$$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $$1$$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $$\Delta $$ , then for each $$k \geq \Delta + 1$$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings are equitable with respect to every G -invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $$\Delta $$ -colourings of graphs with small average degree. Namely, we prove that if $$\Delta \geq 3$$ , G does not contain a clique on $$\Delta + 1$$ vertices and $$\mu $$ is an atomless G -invariant probability measure such that the average degree of G with respect to $$\mu $$ is at most $$\Delta /5$$ , then G has a $$\mu $$ -equitable $$\Delta $$ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.
more »
« less
- PAR ID:
- 10321643
- Date Published:
- Journal Name:
- Forum of Mathematics, Pi
- Volume:
- 9
- ISSN:
- 2050-5086
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We investigate when a Borel graph admits a (Borel or measurable) orientation with outdegree bounded by k k for various cardinals k k . We show that for a probability measure preserving (p.m.p) graph G G , a measurable orientation can be found when k k is larger than the normalized cost of the restriction of G G to any positive measure subset. Using an idea of Conley and Tamuz, we can also find Borel orientations of graphs with subexponential growth; however, for every k k we also find graphs which admit measurable orientations with outdegree bounded by k k but no such Borel orientations. Finally, for special values of k k we bound the projective complexity of Borel k k -orientability for graphs and graphings of equivalence relations. It follows from these bounds that the set of equivalence relations admitting a Borel selector is Σ 2 1 \mathbf {\Sigma }_{2}^{1} in the codes, in stark contrast to the case of smooth relations.more » « less
-
Abstract We study and classify proper q -colourings of the ℤ d lattice, identifying three regimes where different combinatorial behaviour holds. (1) When $$q\le d+1$$ , there exist frozen colourings, that is, proper q -colourings of ℤ d which cannot be modified on any finite subset. (2) We prove a strong list-colouring property which implies that, when $$q\ge d+2$$ , any proper q -colouring of the boundary of a box of side length $$n \ge d+2$$ can be extended to a proper q -colouring of the entire box. (3) When $$q\geq 2d+1$$ , the latter holds for any $$n \ge 1$$ . Consequently, we classify the space of proper q -colourings of the ℤ d lattice by their mixing properties.more » « less
-
ABSTRACT If is a list assignment of colors to each vertex of an ‐vertex graph , then anequitable‐coloringof is a proper coloring of vertices of from their lists such that no color is used more than times. A graph isequitably‐choosableif it has an equitable ‐coloring for every ‐list assignment . In 2003, Kostochka, Pelsmajer, and West (KPW) conjectured that an analog of the famous Hajnal–Szemerédi Theorem on equitable coloring holds for equitable list coloring, namely, that for each positive integer every graph with maximum degree at most is equitably ‐choosable. The main result of this paper is that for each and each planar graph , a stronger statement holds: if the maximum degree of is at most , then is equitably ‐choosable. In fact, we prove the result for a broader class of graphs—the class of the graphs in which each bipartite subgraph with has at most edges. Together with some known results, this implies that the KPW Conjecture holds for all graphs in , in particular, for all planar graphs. We also introduce the new stronger notion ofstrongly equitable(SE, for short) list coloring and prove all bounds for this parameter. An advantage of this is that if a graph is SE ‐choosable, then it is both equitably ‐choosable and equitably ‐colorable, while neither of being equitably ‐choosable and equitably ‐colorable implies the other.more » « less
-
null (Ed.)Abstract In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph $$G$$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $$k$$; in addition, if $$G$$ is $$2$$-connected and non-bipartite, then it contains cycles of all lengths modulo $$k$$. 2. For all $$k\geq 3$$, every $$k$$-connected graph contains a cycle of length zero modulo $$k$$. 3. Every $$3$$-connected non-bipartite graph with minimum degree at least $k+1$ contains $$k$$ cycles of consecutive lengths. 4. Every graph with chromatic number at least $k+2$ contains $$k$$ cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/fmp.2021.12
