Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.04993 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915328079953920 |
|---|---|
| author | Boyer, Geoffrey Kuenzel, Kirsti Lyle, Jeremy Pellico, Ryan |
| author_facet | Boyer, Geoffrey Kuenzel, Kirsti Lyle, Jeremy Pellico, Ryan |
| contents | A graph $G$ is said to be well-hued if every maximal $k$-colorable subgraph of $G$ has the same order $a_k$. Therefore, if $G$ is well-hued, we can associate with $G$ a sequence $\{a_k\}$. Necessary and sufficient conditions were given as to when a sequence $\{a_k\}$ is realized by a well-hued graph. Further, it was conjectured there is only one connected well-hued graph with $a_2 = a_1 + 2$ for every $a_1 \ge 4$. In this paper, we prove this conjecture as well as characterize nearly all well-hued graphs with $a_1=2$. We also investigate when both $G$ and its complement are well-hued. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_04993 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Well-hued graphs with first difference two Boyer, Geoffrey Kuenzel, Kirsti Lyle, Jeremy Pellico, Ryan Combinatorics 05C15, 05C76 A graph $G$ is said to be well-hued if every maximal $k$-colorable subgraph of $G$ has the same order $a_k$. Therefore, if $G$ is well-hued, we can associate with $G$ a sequence $\{a_k\}$. Necessary and sufficient conditions were given as to when a sequence $\{a_k\}$ is realized by a well-hued graph. Further, it was conjectured there is only one connected well-hued graph with $a_2 = a_1 + 2$ for every $a_1 \ge 4$. In this paper, we prove this conjecture as well as characterize nearly all well-hued graphs with $a_1=2$. We also investigate when both $G$ and its complement are well-hued. |
| title | Well-hued graphs with first difference two |
| topic | Combinatorics 05C15, 05C76 |
| url | https://arxiv.org/abs/2506.04993 |