Abstract
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 (\( k \)-rs) colouring of a graph \( G \) is a function \( f:V(G)\rightarrow \{0,1,\dots ,k\,-\,1\} \) such that (i) \( f(x)\ne 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\ge 3 \), it is NP-complete to decide whether a given planar bipartite graph of maximum degree \( k \) and girth at least six is \( k \)-rs colourable, and thereby answer a problem posed by Shalu and Sandhya (Graphs and Combinatorics 2016). In addition, we design an \( O(n^3) \) algorithm to test whether a chordal graph is 3-rs colourable.
First author is supported by SERB (DST), MATRICS scheme MTR/2018/000086.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Albertson, M.O., Chappell, G.G., Kierstead, H.A., Kündgen, A., Ramamurthi, R.: Coloring with no 2-colored \(P_4\)’s. Electron. J. Comb. 11(1), 26 (2004)
Almeter, J., Demircan, S., Kallmeyer, A., Milans, K.G., Winslow, R.: Graph 2-rankings. Graphs Comb. 35(1), 91–102 (2019). https://doi.org/10.1007/s00373-018-1979-4
Bodlaender, H.L., et al.: Rankings of graphs. SIAM J. Discrete Math. 11(1), 168–181 (1998). https://doi.org/10.1137/S0895480195282550
Bozdağ, D., Çatalyürek, Ü.V., Gebremedhin, A.H., Manne, F., Boman, E.G., Özgüner, F.: Distributed-memory parallel algorithms for distance-2 coloring and related problems in derivative computation. SIAM J. Sci. Comput. 32(4), 2418–2446 (2010). https://doi.org/10.1137/080732158
Curtis, A.R., Powell, M.J., Reid, J.K.: On the estimation of sparse Jacobian matrices. J. Inst. Math. Appl. 13(1), 117–120 (1974). https://doi.org/10.1093/imamat/13.1.117
Dereniowski, D.: Rank coloring of graphs. In: Kubale, M. (ed.) Graph Colorings, pp. 79–93, Chap. 6. American Mathematical Society (2004). https://doi.org/10.1090/conm/352/06
Gebremedhin, A., Nguyen, D., Patwary, M.M.A., Pothen, A.: ColPack: software for graph coloring and related problems in scientific computing. ACM Trans. Math. Softw. (TOMS) 40 (2013). https://doi.org/10.1145/2513109.2513110
Gebremedhin, A.H., Manne, F., Pothen, A.: What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev. 47(4), 629–705 (2005). https://doi.org/10.1137/S0036144504444711
Karpas, I., Neiman, O., Smorodinsky, S.: On vertex rankings of graphs and its relatives. Discrete Math. 338(8), 1460–1467 (2015). https://doi.org/10.1016/j.disc.2015.03.008
Katchalski, M., McCuaig, W., Seager, S.: Ordered colourings. Discrete Math. 142(1–3), 141–154 (1995). https://doi.org/10.1016/0012-365X(93)E0216-Q
Lyons, A.: Acyclic and star colorings of cographs. Discrete Appl. Math. 159(16), 1842–1850 (2011). https://doi.org/10.1016/j.dam.2011.04.011
Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discrete Comput. Geom. 26(4), 573–590 (2001). https://doi.org/10.1007/s00454-001-0047-6
Powell, M., Toint, P.L.: On the estimation of sparse Hessian matrices. SIAM J. Numer. Anal. 16(6), 1060–1074 (1979). https://doi.org/10.1137/0716078
Scheffler, P.: Node ranking and searching on graphs. In: 3rd Twente Workshop on Graphs and Combinatorial Optimization, Memorandum No. 1132 (1993)
Shalu, M.A., Sandhya, T.P.: Star coloring of graphs with girth at least five. Graphs Comb. 32(5), 2121–2134 (2016). https://doi.org/10.1007/s00373-016-1702-2
West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Shalu, M.A., Antony, C. (2020). Complexity of Restricted Variant of Star Colouring. In: Changat, M., Das, S. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2020. Lecture Notes in Computer Science(), vol 12016. Springer, Cham. https://doi.org/10.1007/978-3-030-39219-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-39219-2_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39218-5
Online ISBN: 978-3-030-39219-2
eBook Packages: Computer ScienceComputer Science (R0)