Local measures of interval edge-uncolorability
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 K3. 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.
Related
- Sparse empirical measures for non-statistical interval maps with two neutral fixed points
- Edge ideals of complements of a class of circular interval graphs
- Invariant Measures on Smooth Algebraic Groups over Higher Local Fields
- Symbolic depth functions of edge ideals via local graph structure
- Optimal Mixing for Local Edge-Coloring Dynamics on Trees
BibTeX
@misc{casselgren2026local,
title = {{Local measures of interval edge-uncolorability}},
author = {Carl Johan Casselgren and Petros A. Petrosyan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15873},
eprint = {2609.15873},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15873},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Local measures of interval edge-uncolorability
AU - Carl Johan Casselgren
AU - Petros A. Petrosyan
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.15873
UR - https://arxiv.org/abs/2609.15873
AB - 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.
ER -