Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.13494 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916943610511360 |
|---|---|
| author | V., Ullas Chandran S. Di Stefano, Gabriele S., Haritha Thomas, Elias John Tuite, James |
| author_facet | V., Ullas Chandran S. Di Stefano, Gabriele S., Haritha Thomas, Elias John Tuite, James |
| contents | In this paper we consider a colouring version of the general position problem. The \emph{$\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_13494 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Colouring a graph with position sets V., Ullas Chandran S. Di Stefano, Gabriele S., Haritha Thomas, Elias John Tuite, James Combinatorics In this paper we consider a colouring version of the general position problem. The \emph{$\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. |
| title | Colouring a graph with position sets |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.13494 |