The complexity of the empire colouring problem for linear forests

McGrae, Andrew RA and Zito, Michele (2013) The complexity of the empire colouring problem for linear forests. DISCRETE MATHEMATICS, 313 (11). pp. 1248-1255.

Text draft-els.pdf - Author Accepted Manuscript Download (225kB)

Abstract

Let r and s be fixed positive integers. Assume that the n vertices of a planar graph are partitioned into blocks (or empires) each containing exactly r vertices. The (s,r)-colouring problem (s- COLr) asks for a colouring of the vertices of the graph that uses at most s colours, never assigns the same colour to adjacent vertices in different empires and, conversely, assigns the same colour to all vertices in the same empire, disregarding adjacencies. For r=1 the problem coincides with the classical vertex colouring problem on planar graphs. The generalization for r≥2 was defined by Percy Heawood in 1890 in the same paper in which he refuted a previous "proof" of the famous Four Colour Theorem. In a recent paper we have shown that if s≥3, s- COL r is NP-hard for linear forests if s<r. Furthermore, the hardness extends to s<6r-3 (resp. s<7) when r≥3(resp. for r=2) for arbitrary planar graphs. For trees, our argument entails a nice dichotomy: s- COL r is NP-hard for s 3,.,2r-1 and solvable in polynomial time for any other positive value of s. In this paper we argue that linear forests do not make the problem any easier, even for small values of r. We prove that the s- COLr problem is NP-hard for linear forests even if r=2 and s=3, or r=3 and sε{3,4}. © 2012 Elsevier B.V. All rights reserved.

Item Type:	Article
Additional Information:	## TULIP Type: Articles/Papers (Journal) ##
Uncontrolled Keywords:	Colouring, Planar graphs, NP-hardness, Algorithms
Depositing User:	Symplectic Admin
Date Deposited:	09 Feb 2017 10:41
Last Modified:	19 Jan 2023 07:19
DOI:	10.1016/j.disc.2012.06.010
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005660