On the interval coloring impropriety of graphs
| Autor: | Carr, MacKenzie, Cho, Eun-Kyung, Crawford, Nicholas, Iršič, Vesna, Pai, Leilani, Robinson, Rebecca |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 \in 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 $\mu_{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 $\mu_{int}(G)\leq 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$. Comment: 17 pages, 8 figures, 7 tables |
| Databáze: | arXiv |
| Externí odkaz: |
|