On local and semi-matching colorings of split graphs

A semi-matching coloring of a finite simple graph $G=(V,E)$ is a mapping $\varphi$ from $V$ to $\lbrace 1,\dotsc,k \rbrace$ such that (i) every color class is an independent set, and (ii) the edge set of the graph induced by the union of any two consecutive color classes is a matching. A semi-matching coloring $\varphi$ is a local coloring if, in addition, (iii) the union of any three consecutive color classes induces a triangle-free subgraph of $G$. In this paper, we give two counterexamples and one positive solution to three problems arisen in recent papers of You, Cao, Wang. In particular, we show that the local and semi-matching coloring problems are NP-complete on the class of split graphs.

Keywords

graph coloring, split graph, algorithmic complexity

2010 Mathematics Subject Classification

05C38, 68Q17

Full Text (PDF format)

Received 21 December 2021

Received revised 17 July 2022

Accepted 11 October 2022

Published 26 April 2023