Colouring a graph with position sets
In this paper we consider a colouring version of the general position problem. The gp-chromatic number is the smallest number of colours needed to colour V(G) such that each colour class has the no-three-in-line property. We determine bounds on this colouring number in terms of the diameter, general position number, size, chromatic number, cochromatic number and total domination number and prove realisation results. We also determine it for several graph classes, including Kneser graphs K(n,2), line graphs of complete graphs, complete multipartite graphs, block graphs and Cartesian products. We also show that the gp-colouring problem is NP-complete.
Authors
- Gabriele Di Stefano (ORCID: https://orcid.org/0000-0003-4521-8356)
- James Tuite (ORCID: https://orcid.org/0000-0003-2604-7491)
- Elias John Thomas (ORCID: https://orcid.org/0000-0003-0598-4726)
- Ullas Chandran S.V. (ORCID: https://orcid.org/0000-0002-2081-9094)
- S. Haritha
Institutions
- University of Kerala (IN)
- University of L'Aquila (IT)
- Klaipėda University (LT)
Publication Details
- Journal
- Ars Mathematica Contemporanea
- Published
- 2025-11-13
- DOI
- https://doi.org/10.26493/1855-3974.3454.a3c
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Istituto Nazionale di Alta Matematica "Francesco Severi"
- London Mathematical Society
- Gruppo Nazionale per il Calcolo Scientifico
- Engineering and Physical Sciences Research Council