Star colouring of bounded degree graphs and regular graphs

DOI10.1016/j.disc.2022.112850zbMath1486.05104OpenAlexW4213456162MaRDI QIDQ2124639

Cyriac Antony, M. A. Shalu

Publication date: 11 April 2022

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

Full work available at URL: https://doi.org/10.1016/j.disc.2022.112850

zbMATH Keywords

complexityregular graphspartitioning problemsstar colouringlocally checkable vertex subset

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Related Items (1)

Hardness transitions and uniqueness of acyclic colouring

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Star coloring of cubic graphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• Acyclic and \(k\)-distance coloring of the grid
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Some simplified NP-complete graph problems
• Graph 2-rankings
• Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
• Coloring with no 2-colored \(P_4\)'s
• 3-colouring AT-free graphs in polynomial time
• On Eulerian orientations of even-degree hypercubes
• Distance-two coloring of sparse graphs
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Star coloring of graphs
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• On Approximately Counting Colorings of Small Degree Graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Equitable Coloring
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Star chromatic index of subcubic multigraphs
• Kernelization
• NP completeness of finding the chromatic index of regular graphs
• 6-Star-Coloring of Subcubic Graphs
• What Color Is Your Jacobian? Graph Coloring for Computing Derivatives
• Acyclic colorings of planar graphs

This page was built for publication: Star colouring of bounded degree graphs and regular graphs