On the complexity of local-equitable coloring in claw-free graphs with small degree (Q6616437)

Let \(G\) be a graph. A set \(C\subset V(G)\) is a clique if the subgraph of \(G\) induced by \(C\) is a complete graph and a clique is maximal if it is not contained in any larger clique. A map \(c:V(G)\rightarrow \{1,\dots,k\}\) is a \(k\)-coloring (where two adjacent vertices can have the same value) and sets \(V_i=\{v\in V(G):c(v)=i\}\), \(i\in\{1,\dots,k\}\), are color classes of \(c\). A \(k\)-coloring is called a local-equitable \(k\)-coloring if \(||V_i\cap C|-|V_j\cap C||\leq 1\) for every maximal clique \(C\) and any \(i\leq i<j\leq k\).\N\NA complete bipartite graph \(K_{1,3}\) is called a claw and a graph \(G\) is claw-free if \(G\) posses no induced subgraph isomorphic to a claw.\N\NThis contribution is a study of claw-free graphs with maximum degree of at most four with respect to local-equitable \(2\)-coloring. In particular, a linear algorithm is presented that answers the question if a claw-free graph with maximum degree at most four is local-equitable \(2\)-colorable or not.