2024/08/08 by Seunghun Lee, Lee, Seunghun
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2408.04393
openalex publication_date 2024/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a graph G, we call an edge coloring of G an improper interval edge coloring if for every v∈ V(G) the colors, which are integers, of the edges incident with v form an integral interval. The interval coloring impropriety of G, denoted by μint(G), is the smallest value k such that G has an improper interval edge coloring where at most k edges of G with a common endpoint have the same color. The purpose of this note is to communicate solutions to two previous questions on interval coloring impropriety, mainly regarding planar graphs. First, we prove μint(G) ≤ 2 for every outerplanar graph G. This confirms the conjecture by Casselgren and Petrosyan in the affirmative. Secondly, we prove that for each k≥ 2, the interval coloring impropriety of k-trees is unbounded. This refutes the conjecture by Carr, Cho, Crawford, Iršič, Pai and Robinson.