On the interval coloring impropriety of graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916266654040064 |
|---|---|
| author | Carr, MacKenzie Cho, Eun-Kyung Crawford, Nicholas Iršič, Vesna Pai, Leilani Robinson, Rebecca |
| author_facet | Carr, MacKenzie Cho, Eun-Kyung Crawford, Nicholas Iršič, Vesna Pai, Leilani Robinson, Rebecca |
| contents | 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 $μ_{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)\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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_14881 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the interval coloring impropriety of graphs Carr, MacKenzie Cho, Eun-Kyung Crawford, Nicholas Iršič, Vesna Pai, Leilani Robinson, Rebecca 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 $μ_{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)\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$. |
| title | On the interval coloring impropriety of graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2312.14881 |