Linear-time certifying algorithm conjecture for star coloring of split graphs

Let $G=(K,S)$ be a split graph, where $K$ is a clique and $S$ is an independent set. A star $k$-coloring is a star coloring using at most $k$ colors.

Linear-time certifying algorithm conjecture. For every fixed positive integer $k$, there is a certifying algorithm that runs in time

$$O(|V|+|E|)$$

to determine whether an input split graph $G$ admits a star $k$-coloring.

The conjecture is motivated by explicit certifying algorithms for the cases treated earlier in the paper and by the apparent extendability of their structural proofs to every fixed $k$. The supplied text does not provide a proof for arbitrary $k$.