On structural parameterizations of star coloring

DOI10.1007/978-3-031-25211-2_12MaRDI QIDQ6132531zbMATH OpenOpenAlexFDO

Authors Sriram Bhyravarapu, I. Vinod Reddy

Publication date 17 August 2023

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

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: A Star Coloring of a graph G is a proper vertex coloring such that every path on four vertices uses at least three distinct colors. The minimum number of colors required for such a star coloring of G is called star chromatic number, denoted by chi_s(G). Given a graph G and a positive integer k, the STAR COLORING PROBLEM asks whether $G$ has a star coloring using at most k colors. This problem is NP-complete even on restricted graph classes such as bipartite graphs. In this paper, we initiate a study of STAR COLORING from the parameterized complexity perspective. We show that STAR COLORING is fixed-parameter tractable when parameterized by (a) neighborhood diversity, (b) twin-cover, and (c) the combined parameters clique-width and the number of colors.

Cites work

• scientific article; zbMATH DE number 1688572 (Why is no real title available?)
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• A polynomial time algorithm to find the star chromatic index of trees
• Acyclic and star colorings of cographs
• Acyclic colorings of planar graphs
• Algorithmic meta-theorems for restrictions of treewidth
• An application of simultaneous diophantine approximation in combinatorial optimization
• Coloring with no 2-colored \(P_4\)'s
• Efficient computation of sparse hessians using coloring and automatic differentiation
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Estimation of sparse hessian matrices and graph coloring problems
• Graph minors. I. Excluding a forest
• Integer Programming with a Fixed Number of Variables
• Intractability of clique-width parameterizations
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minkowski's Convex Body Theorem and Integer Programming
• On structural parameterizations of star coloring
• Parameterized algorithms
• Parameterized pre-coloring extension and list coloring problems
• Star chromatic index of subcubic multigraphs
• The complexity of star colouring in bounded degree graphs and regular graphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Upper bounds to the clique width of graphs

Cited in

(11)

• Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
• A polyhedral investigation of star colorings
• Block colourings of star systems
• scientific article; zbMATH DE number 5239161 (Why is no real title available?)
• On structural parameterizations of star coloring
• scientific article; zbMATH DE number 6124450 (Why is no real title available?)
• The complexity of star colouring in bounded degree graphs and regular graphs
• Hardness transitions of star colouring and restricted star colouring
• The Star and Biclique Coloring and Choosability Problems
• A polynomial time algorithm to find the star chromatic index of trees
• scientific article; zbMATH DE number 6178423 (Why is no real title available?)

This page was built for publication: On structural parameterizations of star coloring

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