2024/08/24 by Ullas Chandran S. V., Gabriele Di Stefano, V., Ullas Chandran S. +7 · 1 citation
Computer Science · Physics and Astronomy · Psychology · #Advanced Graph Theory Research #Color Science and Applications #Color perception and design #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2408.13494
openalex publication_date 2024/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 the vertices of the graph 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 the \gp -chromatic number of several graph classes, including Kneser graphs K(n,2), line graphs of complete graphs, complete multipartite graphs, block graphs and Cartesian products. Finally, we show that the \gp -colouring problem is NP-complete.