Scholarlink

<p>This study presents the nature of the relationship between Set Dominating Coloring Sets (SDCS) and Acyclic Colorings (ACs), two paradigms that have traditionally been studied in isolation but are structurally linked. While SDCS aims to find a dominating set (DS) of vertices that induces a properly colored subgraph, AC is concerned with proper coloring (PC) given the additional constraint of not allowing any 2-colored cycles. The objective of this study is to connect these two paradigms, because many real-world systems, including communication networks, scheduling, and fault-tolerant architectures, must incorporate both domination and acyclicity. The paper tries to find occasions when a set dominating coloring is also an AC and vice versa, from which additional new insights into their interplay are presented. A comparative analysis of their structural properties, parameter bounds, and complexity aspects is presented. The study’s novelty lies in the acyclic set dominating chromatic number, a new metric that combines acyclicity and dominance constraints. Its behavior within selected classes of graphs is studied. Theoretical formulations and examples provided in the research illustrate possible intersections, divergences, and applications, therefore providing a launchpad towards further development in both domination theory and more advanced coloring techniques.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A study on the relationship between set dominating coloring set and acyclic coloring

  • 期刊论文

  • 发表日期：

    2026年3月27日

查看全文
  • M. Vidhyashankar,
  • P. Solairani

摘要

This study presents the nature of the relationship between Set Dominating Coloring Sets (SDCS) and Acyclic Colorings (ACs), two paradigms that have traditionally been studied in isolation but are structurally linked. While SDCS aims to find a dominating set (DS) of vertices that induces a properly colored subgraph, AC is concerned with proper coloring (PC) given the additional constraint of not allowing any 2-colored cycles. The objective of this study is to connect these two paradigms, because many real-world systems, including communication networks, scheduling, and fault-tolerant architectures, must incorporate both domination and acyclicity. The paper tries to find occasions when a set dominating coloring is also an AC and vice versa, from which additional new insights into their interplay are presented. A comparative analysis of their structural properties, parameter bounds, and complexity aspects is presented. The study’s novelty lies in the acyclic set dominating chromatic number, a new metric that combines acyclicity and dominance constraints. Its behavior within selected classes of graphs is studied. Theoretical formulations and examples provided in the research illustrate possible intersections, divergences, and applications, therefore providing a launchpad towards further development in both domination theory and more advanced coloring techniques.