The strong pseudoachromatic number of a graph (Q2811807)

A strong-\(k\)-coloring of a graph \(G\) is a (necessarily not proper) \(k\)-coloring \(\gamma\) such that for any two (not necessarily distinct) colors \(i\) and \(j\), there is at least one edge \(uv\) in \(G\) with \(\gamma(u)=i\) and \(\gamma(v)=j\). The maximum \(k\) for which \(G\) admits a strong-\(k\)-coloring is the strong pseudoachromatic number of \(G\), denoted \(\psi^*(G)\).NEWLINENEWLINEThe authors determine the strong pseudoachromatic number of some special classes of graphs such as complete graphs, complete multipartite graphs, paths, cycles or wheels. They study the variation of this parameter with respect to vertex or edge deletion and characterize the class of graphs \(\mathcal{G}_1\) that satisfy \(\psi^*(G\vee H)=\psi^*(G)+\psi^*(H)\) for every \(G,H\in\mathcal{G}_1\), where \(G\vee H\) denotes the join of \(G\) and \(H\). They also characterize the class of graphs \(\mathcal{G}_2\) that satisfy \(\psi(G\vee H)=\psi(G)+\psi(H)\) for every \(G, H\in\mathcal{G}_2\), where \(\psi(G)\) denotes the pseudoachromatic number of \(G\).