Well-hued graphs with first difference two

Geoffrey Boyer; Kirsti Kuenzel; Jeremy Lyle; Ryan Pellico

paper

Well-hued graphs with first difference two

arXiv:2506.04993

Abstract

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} \geq 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.