Repozytorium publikacji - Politechnika Gdańska

We consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.

Autorzy

• Hanna Furmańczyk,
• prof. dr hab. inż. Marek Kubale link otwiera się w nowej karcie