Colouring a dominating set without conflicts: q-subset square colouring

DOI10.1016/J.TCS.2023.114160MaRDI QIDQ6077071zbMATH OpenFDO

Authors V. P. Abidha, Pradeesha Ashok, Avi Tomar, Dolly Yadav

Publication date 17 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

dominating setgraph colouringparameterized algorithmsquare colouringsubset square colouring

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The emph{Square Colouring} of a graph $G$ refers to colouring of vertices of a graph such that any two distinct vertices which are at distance at most two receive different colours. In this paper, we initiate the study of a related colouring problem called the emph{subset square colouring} of graphs. Broadly, the subset square colouring of a graph studies the square colouring of a dominating set of a graph using $q$ colours. Here, the aim is to optimize the number of colours used. This also generalizes the well-studied Efficient Dominating Set problem. We show that the q-Subset Square Colouring problem is NP-hard for all values of $q$ even on bipartite graphs and chordal graphs. We further study the parameterized complexity of this problem when parameterized by a number of structural parameters. We further show bounds on the number of colours needed to subset square colour some graph classes.

Recommendations

• Coloring a dominating set without conflicts: \(q\)-subset square coloring
• Conflict free colorings of (strongly) almost disjoint set-systems
• On conflict-free multi-coloring
• Conflict-free colourings of graphs and hypergraphs
• Conflict-free colouring of graphs
• Exact square coloring of certain classes of graphs: complexity and algorithms
• Conflict-Free Colorings of Rectangles Ranges
• Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
• Conflict-free coloring and its applications

Cites work

• A c^k n 5-approximation algorithm for treewidth
• Algorithmic graph theory and perfect graphs
• An optimal square coloring of planar graphs
• Bipartite permutation graphs
• Chromatic graph theory
• Coloring a dominating set without conflicts: \(q\)-subset square coloring
• Coloring the square of a planar graph
• Complexity of conflict-free colorings of graphs
• Conflict-free coloring of graphs
• Dominating sets for split and bipartite graphs
• Domination numbers of planar graphs
• Hardness of r-dominating set on graphs of diameter (r + 1)
• scientific article; zbMATH DE number 6515825 (Why is no real title available?)
• scientific article; zbMATH DE number 4085682 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• Kernelization Lower Bounds by Cross-Composition
• Labelling Graphs with a Condition at Distance 2
• Maximal independent sets in caterpillar graphs
• On the Harmonious Coloring of Graphs
• Parameterized algorithms
• Parameterized Algorithms for Modular-Width
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Parameterized Complexity of Conflict-Free Graph Coloring
• Structural parameterization for minimum conflict-free colouring
• Weighted efficient domination problem on some perfect graphs

This page was built for publication: Colouring a dominating set without conflicts: \(q\)-subset square colouring

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