Skip to content
Preprint

On-line majority edge-colourings of graphs

Sep 2026 · 0 citations · 16 references
Mathematics

Abstract

A majority edge-colouring of a graph $G$ is a colouring of the edges of $G$ such that, for every vertex $v$ of $G$, at most half of the edges incident with $v$ receive the same colour. This notion was introduced by Bock et al. in 2023, who proved that every graph of minimum degree at least $2$ has a majority $4$-edge-colouring. We investigate an on-line variant of majority edge-colouring in which the graph is revealed by the Presenter edge-by-edge and the Algorithm must colour each edge immediately and irrevocably. In particular. we prove that the greedy strategy, which uses at most five colours, is optimal among on-line algorithms if $\delta = O(\frac{\log n}{\log\log n})$. We further extend our results to $1/k$-majority edge-colourings.

View source

Similar papers

Preprint Sep 2026

Strong Edge Colouring of Disk Graphs: A 6-Approximation and an Improved Unit-Disk Bound

A strong edge colouring of a graph $G$ is an edge colouring in which every colour class is an induced matching. The minimum number of colours is the strong chromatic index $\chi'_s(G)$. If each edge $e$ is assigned a list $L'(e)$ and its colour must belong to $L'(e)$, the corresponding parameter is the strong list chro...

Sandip Das, Sk Samim Islam, A. Mohapatra et al. · 0 citations
Preprint Sep 2026

Rainbow connecting $2$-colorings of super-Dirac graphs

Let $G$ be a graph with minimum degree $\delta(G)\ge|V(G)|/2$. Can we color the edges of $G$ with red and blue so that every pair of non-adjacent vertices is connected by a path consisting of exactly one red edge and one blue edge? We provide an affirmative answer to this question for a class of graphs that are ``close...

J'anos Bar'at, Simona Boyadzhiyska, Andrea Freschi · 0 citations
Preprint Aug 2026

Three-edge-coloring apex cubic graphs

A graph $G$ is \emph{apex} if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, gen...

Yuta Inoue, K. Kawarabayashi, Rintaro Matsuo et al. · 1 citation
Preprint Sep 2026

Sharp Rainbow Path Covers in Dense and Complete Multipartite Graphs

A path in a properly edge-colored graph is rainbow if its edges have pairwise distinct colors. For a proper edge-coloring $c$ of a graph $G$, let $\operatorname{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\operatorname{rpc}(G)$ be the maximum of $\operatorname{rpc}(G,c)$ over all...

Xiao-Chuan Liu, Bo-Yan Xu, Xu Yang · 0 citations
Preprint Oct 2026

Elementary graphs are chromatic-choosable

A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chv\'atal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipart...

N. Narayanan, Nandana K. Vasudevan, K. Somasundaram · 0 citations
Preprint Sep 2026

Nearly optimal packings of equally sized rainbow forests

A forest in an edge-colored graph is rainbow if its edges have pairwise distinct colors. We prove that for every $\varepsilon>0$ and all sufficiently large integers $m$, every properly edge-colored simple graph with $km$ edges, where $1\leq k\leq 2m$ and every color class has size at most $m$, contains at least $(1-\va...

Bo-Yan Xu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.