{"id":"arxiv/2609.15873","url":"https://arxiv.org/abs/2609.15873","tags":["math.CO"],"score":0,"title":"Local measures of interval edge-uncolorability","domain":"math.CO","source":"arxiv","authors":["Carl Johan Casselgren","Petros A. Petrosyan"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}