The complexity of the empire colouring problem for linear forests


McGrae, Andrew RA and Zito, Michele ORCID: 0009-0000-7182-3758 (2013) The complexity of the empire colouring problem for linear forests. DISCRETE MATHEMATICS, 313 (11). pp. 1248-1255. ISSN 0012-365X, 1872-681X

[thumbnail of draft-els.pdf] 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- COL<inf>r</inf>) 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 <inf>r</inf> 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 <inf>r</inf> 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- COL<inf>r</inf> 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: 07 Jun 2025 17:09
DOI: 10.1016/j.disc.2012.06.010
Related Websites:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3005660
Altmetric
CORE (COnnecting REpositories)