Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.04393 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914905752338432 |
|---|---|
| author | Lee, Seunghun |
| author_facet | Lee, Seunghun |
| contents | For a graph $G$, we call an edge coloring of $G$ an \textit{improper} \textit{interval edge coloring} if for every $v\in V(G)$ the colors, which are integers, of the edges incident with $v$ form an integral interval. The \textit{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) \leq 2$ for every outerplanar graph $G$. This confirms the conjecture by Casselgren and Petrosyan in the affirmative. Secondly, we prove that for each $k\geq 2$, the interval coloring impropriety of $k$-trees is unbounded. This refutes the conjecture by Carr, Cho, Crawford, Iršič, Pai and Robinson. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04393 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The interval coloring impropriety of planar graphs Lee, Seunghun Combinatorics For a graph $G$, we call an edge coloring of $G$ an \textit{improper} \textit{interval edge coloring} if for every $v\in V(G)$ the colors, which are integers, of the edges incident with $v$ form an integral interval. The \textit{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) \leq 2$ for every outerplanar graph $G$. This confirms the conjecture by Casselgren and Petrosyan in the affirmative. Secondly, we prove that for each $k\geq 2$, the interval coloring impropriety of $k$-trees is unbounded. This refutes the conjecture by Carr, Cho, Crawford, Iršič, Pai and Robinson. |
| title | The interval coloring impropriety of planar graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.04393 |