\input zb-basic
\input zb-ioport
\iteman{io-port 06101498}
\itemau{Couetoux, Basile; Monnot, J\'erome; Toubaline, Sonia}
\itemti{Complexity results for the empire problem in collection of stars.}
\itemso{Lin, Guohui (ed.), Combinatorial optimization and applications. 6th international conference, COCOA 2012, Banff, AB, Canada, August 5--9, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31769-9/pbk). Lecture Notes in Computer Science 7402, 73-82 (2012).}
\itemab
Summary: We study the empire problem, a generalization of the coloring problem to maps on two-dimensional compact surface whose genus is positive. Given a planar graph with a certain partition of the vertices into blocks of size $r$, for a given integer $r$, the problem consists of deciding if $s$ colors are sufficient to color the vertices of the graph such that vertices of the same block have the same color and vertices of two adjacent blocks have different colors. In this paper, we prove that given a 5-regular graph, deciding if there exists a 4-coloration is NP-complete. Also, we propose conditional NP-completeness results for the empire problem when the graph is a collection of stars. A star is a graph isomorphic to $K _{1,q }$ for some $q \geq 1$. More exactly, we prove that for $r \geq 2$, if the $(2r - 1)$-coloring problem in $2r$-regular connected graphs is NP-complete, then the empire problem for blocks of size $r + 1$ and $s = 2r - 1$ is NP-complete for forests of $K _{1, r }$. Moreover, we prove that this result holds for $r = 2$. Also for $r \geq 3$, if the $r$-coloring problem $in $(r + 1)-regular graphs is NP-complete, then the empire problem for blocks of size $r + 1$ and $s = r$ is NP-complete for forests of $K _{1, 1} = K _{2}$, i.e., forest of edges. Additionally, we prove that this result is valid for $r = 2$ and $r = 3$. Finally, we prove that these results are the best possible, that is for smallest value of $s$ or $r$, the empire problem in these classes of graphs becomes polynomial.
\itemrv{~}
\itemcc{}
\itemut{empire problem; coloring in regular graphs; NP-completeness; forests of stars}
\itemli{doi:10.1007/978-3-642-31770-5\_7}
\end