تقرير
On the interval coloring impropriety of graphs
| العنوان: | On the interval coloring impropriety of graphs |
|---|---|
| المؤلفون: | Carr, MacKenzie, Cho, Eun-Kyung, Crawford, Nicholas, Iršič, Vesna, Pai, Leilani, Robinson, Rebecca |
| سنة النشر: | 2023 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C15 |
| الوصف: | 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 |
| نوع الوثيقة: | Working Paper |
| الوصول الحر: | http://arxiv.org/abs/2312.14881Test |
| رقم الانضمام: | edsarx.2312.14881 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |