2023/12/22 by MacKenzie Carr, Carr, MacKenzie, Eun‐Kyung Cho +9
Computer Science · Mathematics · #05C15 #1-planar graph #Advanced Graph Theory Research #Appearance of impropriety #Chordal graph #Combinatorics #Combinatorics (math.CO) #Discrete mathematics #Edge coloring #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Graph coloring #Graph power #Interval (graph theory) #Interval graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Multipartite #Pathwidth #Physics #Vertex (graph theory)
paper · pdf · doi:10.48550/arxiv.2312.14881
openalex publication_date 2023/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An improper interval (edge) coloring of a graph G is an assignment of colors to the edges of G satisfying the condition that, for every vertex v ∈ V(G), the set of colors assigned to the edges incident with v forms an integral interval. An interval coloring is k-improper if at most k edges with the same color all share a common endpoint. The minimum integer k such that there exists a k-improper interval coloring of the graph G is the interval coloring impropriety of G, denoted by μint(G). In this paper, we provide a construction of an interval coloring of a subclass of complete multipartite graphs. This provides additional evidence to the conjecture by Casselgren and Petrosyan that μint(G)≤ 2 for all complete multipartite graphs G. Additionally, we determine improved upper bounds on the interval coloring impropriety of several classes of graphs, namely 2-trees, iterated triangulations, and outerplanar graphs. Finally, we investigate the interval coloring impropriety of the corona product of two graphs, G\odot H.