Metraipolis › archive › dc_4e6451cbf083

On Strong Majority Edge Colourings with Few Colours — arXiv:2608.04122

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.04122
License (as archived): CC0-1.0
Archived: 2026-10-31T11:45:56.149Z
SHA-256 of the archived text: a7e20a59ccb91e2bae92117f6b655dee87b4a234437adac6d914bbad83240858
Stable URL of this page: https://metraipolis.com/documento/dc_4e6451cbf083

How to cite

On Strong Majority Edge Colourings with Few Colours — arXiv:2608.04122 — arXiv (en), https://arxiv.org/abs/2608.04122 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_4e6451cbf083 (Metraipolis archive dc_4e6451cbf083, sha256 a7e20a59ccb91e2bae92117f6b655dee87b4a234437adac6d914bbad83240858)

BibTeX

@misc{dc4e6451cbf083,
  title = {On Strong Majority Edge Colourings with Few Colours — arXiv:2608.04122},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.04122},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_4e6451cbf083; sha256 a7e20a59ccb91e2bae92117f6b655dee87b4a234437adac6d914bbad83240858},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.04122. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A strong majority edge colouring of a graph $G$ is an edge colouring in which, for every edge $e$ and every colour $\alpha$, at most half the edges adjacent to $e$ receive colour $\alpha$. Like many related colouring notions, it admits a natural interpretation as a colouring problem for an associated hypergraph. Somewhat surprisingly, although the corresponding hypergraph may have arbitrarily large vertex degrees, a universal finite upper bound on the sufficient number of colours in a strong majority edge colouring exists under a natural modest minimum degree assumption, unlike in several other closely related majority concepts. We in particular prove that every graph $G$ with minimum degree $\delta\ge5$ admits a strong majority edge colouring with three colours, improving both the previously known bound $\delta\ge9$ for three colours and the result showing that four colours suffice whenever $\delta\ge5$. Our result is best possible with respect to the number of colours and the minimum degree assumption. We also introduce a more general framework of strong $1/k$-majority edge colourings and establish corresponding bounds for this setting.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-06 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.04122 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-31T11:35:10.096Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-06?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).