
arXiv: 2309.16624
A $\frac{1}{k}$-majority $l$-edge-colouring of a graph $G$ is a colouring of its edges with $l$ colours such that for every colour $i$ and each vertex $v$ of $G$, at most $\frac{1}{k}$'th of the edges incident with $v$ have colour $i$. We conjecture that for every integer $k\geq 2$, each graph with minimum degree $\delta\geq k^2$ is $\frac{1}{k}$-majority $(k+1)$-edge-colourable and observe that such result would be best possible. This was already known to hold for $k=2$. We support the conjecture by proving it with $2k^2$ instead of $k^2$, which confirms the right order of magnitude of the conjectured optimal lower bound for $\delta$. We at the same time improve the previously known bound of order $k^3\log k$, based on a straightforward probabilistic approach. As this technique seems not applicable towards any further improvement, we use a more direct non-random approach. We also strengthen our result, in particular substituting $2k^2$ by $(\frac{7}{4}+o(1))k^2$. Finally, we provide the proof of the conjecture itself for $k\leq 4$ and completely solve an analogous problem for the family of bipartite graphs.
Coloring of graphs and hypergraphs, 05C15, FOS: Mathematics, Directed graphs (digraphs), tournaments, Mathematics - Combinatorics, Combinatorics (math.CO), majority colouring of a digraph
Coloring of graphs and hypergraphs, 05C15, FOS: Mathematics, Directed graphs (digraphs), tournaments, Mathematics - Combinatorics, Combinatorics (math.CO), majority colouring of a digraph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
