Skip to content
Preprint

Local measures of interval edge-uncolorability

Sep 2026 · 0 citations · 32 references
Mathematics

Abstract

An interval edge coloring of a graph is a proper edge coloring by integers such that the colors on the edges incident with any vertex form an interval of integers. Not all graphs are interval colorable; a simple counterexample is $K_3$. The (interval coloring) deficiency of a graph $G$ is the minimum number of pendant edges whose addition to $G$ yields a graph with an interval edge coloring. In this paper, we introduce and study further measures of how far from being interval colorable a graph is. The local deficiency of a graph $G$ is the smallest number of pendant edges that needs to be added at every vertex of $G$ in order to obtain a graph with an interval edge coloring; we can think of the colors of these added edges as''locally missing''at a vertex. We also study a weaker version of this notion, the weak local deficiency, which informally is the size of a largest set of consecutive integers''locally missing''at a vertex in a proper edge coloring of $G$ minimizing this size. We compare weak local deficiency, local deficiency, and deficiency, and show that the difference can be arbitrarily large in both cases. Moreover, we give concrete examples of graphs whose weak local deficiency (and thus local deficiency) grows with the number of vertices as well as with the maximum degree. We also prove some constructive results on graphs with small weak local deficiency. In particular, all complete multipartite graphs have weak local deficiency at most $2$, and many complete multipartite graphs have weak local deficiency at most $1$. Moreover, bipartite graphs with maximum degree at most $6$, and Eulerian bipartite graphs with maximum degree at most $8$ both have weak local deficiency at most $1$. We conclude the paper by pointing to several open questions for further research.

View source

Similar papers

Preprint Sep 2026

Graph Coloring with Color Preferences

We study graph coloring with color preferences, in which each vertex ranks the available colors. In addition to assigning different colors to adjacent vertices, we require the coloring to be stable: no group of vertices can cyclically exchange their assigned colors so that each strictly prefers its new color to its ori...

Tomohiro Koana, Y. Oh, Hirotaka Yoneda · 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

Superlinear separation between linear and centered colorings

A vertex-coloring of a graph is centered if every connected subgraph has a vertex with a unique color. A vertex-coloring of a graph is linear if every path in the graph has a vertex with a unique color. Let $\chi_{\mathrm{cen}}(G)$ and $\chi_{\mathrm{lin}}(G)$ be the minimum number of colors in a centered (resp. linear...

Jędrzej Hodor, P. Micek · 0 citations
Sep 2026

Vertex-Coloring Edge-Weighting: Kernelization and Generalization

This work shows that both pre-weighted problems have polynomial kernels when parameterized by $k, and shows that both problems are W[1]-hard parameterized by treedepth, answering another question from earlier work.

Shubhada Aute, Fahad Panolan, Geevarghese Philip · 0 citations
Preprint Sep 2026

On-line majority edge-colourings of graphs

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-c...

Pawel Pękała · 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

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