The complexity of star colouring in bounded degree graphs and regular graphs

DOI10.1007/978-3-030-95018-7_7MaRDI QIDQ6102265zbMATH OpenOpenAlexFDO

Authors M. A. Shalu, Cyriac Antony

Publication date 8 May 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-95018-7_7

zbMATH Keywords

complexitygraph coloringstar coloringvertex coloring

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Star colouring of bounded degree graphs and regular graphs
• The complexity of restricted star colouring
• scientific article; zbMATH DE number 2044931
• scientific article; zbMATH DE number 7527896
• Complexity of restricted variant of star colouring
• Acyclic graph coloring and the complexity of the star chromatic number
• A survey on star edge-coloring of graphs
• Star coloring of graphs
• Star coloring of certain graph classes
• On structural parameterizations of star coloring

Cites work

• A polynomial time algorithm to find the star chromatic index of trees
• Acyclic and star colorings of cographs
• Acyclic colorings of planar graphs
• Coloring with no 2-colored \(P_4\)'s
• Colouring graphs when the number of colours is almost the maximum degree
• Complexity of restricted variant of star colouring
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)
• New Acyclic and Star Coloring Algorithms with Application to Computing Hessians
• Star chromatic index of subcubic multigraphs
• Star coloring of cubic graphs
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives

Cited in

(5)

• A polynomial algorithm for finding \((g,f)\)-colorings orthogonal to stars in bipartite graphs
• A generic framework for approximation analysis of greedy algorithms for star bicoloring
• Acyclic, star, and injective colouring: bounding the diameter
• On structural parameterizations of star coloring
• Hardness transitions of star colouring and restricted star colouring

This page was built for publication: The complexity of star colouring in bounded degree graphs and regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102265)