The complexity of restricted star colouring

DOI10.1016/j.dam.2021.05.015zbMath1494.05047arXiv2108.02979OpenAlexW3168876418MaRDI QIDQ2161257

Shalu M. A., Cyriac Antony

Publication date: 4 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2108.02979

zbMATH Keywords

complexitygraph colouringvertex rankingstar colouringrestricted star colouringunique superior colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Uses Software

• ColPack

Cites Work

• Unnamed Item
• Star coloring of graphs with girth at least five
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Acyclic and star colorings of cographs
• Complexity of restricted variant of star colouring
• On an edge ranking problem of trees and graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Graph 2-rankings
• Coloring with no 2-colored \(P_4\)'s
• Ordered colourings
• On vertex rankings of graphs and its relatives
• Coloring the square of an outerplanar graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Distributed-Memory Parallel Algorithms for Distance-2 Coloring and Related Problems in Derivative Computation
• ColPack
• The Role of Elimination Trees in Sparse Factorization
• New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
• On the Estimation of Sparse Hessian Matrices
• Rankings of Graphs
• Graph Colorings
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• Hard tiling problems with simple tiles