تقرير
Complexity of Restricted Star Colouring
| العنوان: | Complexity of Restricted Star Colouring |
|---|---|
| المؤلفون: | A., Shalu M., Antony, Cyriac |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics |
| الوصف: | Restricted star colouring is a variant of star colouring introduced to design heuristic algorithms to estimate sparse Hessian matrices. For $k\in\mathbb{N}$, a $k$-restricted star colouring ($k$-rs colouring) of a graph $G$ is a function $f:V(G)\to{0,1,\dots,k-1}$ such that (i)$f(x)\neq f(y)$ for every edge $xy$ of G, and (ii) there is no bicoloured 3-vertex path ($P_3$) in $G$ with the higher colour on its middle vertex. We show that for $k\geq 3$, it is NP-complete to test whether a given planar bipartite graph of maximum degree $k$ and arbitrarily large girth admits a $k$-rs colouring, and thereby answer a problem posed by Shalu and Sandhya (Graphs and Combinatorics, 2016). In addition, it is NP-complete to test whether a 3-star colourable graph admits a 3-rs colouring. We also prove that for all $\epsilon > 0$, the optimization problem of restricted star colouring a 2-degenerate bipartite graph with the minimum number of colours is NP-hard to approximate within $n^{(1/3)-\epsilon}$. On the positive side, we design (i) a linear-time algorithm to test 3-rs colourability of trees, and (ii) an $O(n^3)$-time algorithm to test 3-rs colourability of chordal graphs. Comment: Discrete Applied Mathematics (2021) |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.1016/j.dam.2021.05.015. |
| URL الوصول: | http://arxiv.org/abs/2108.02979 |
| رقم الأكسشن: | edsarx.2108.02979 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.1016/j.dam.2021.05.015. |
|---|