Extremal Results on Conflict-free Coloring
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914142848286720 |
|---|---|
| author | Bhyravarapu, Sriram Gupta, Shiwali Kalyanasundaram, Subrahmanyam Mathew, Rogers |
| author_facet | Bhyravarapu, Sriram Gupta, Shiwali Kalyanasundaram, Subrahmanyam Mathew, Rogers |
| contents | A conflict-free open neighborhood coloring of a graph is an assignment of colors to the vertices such that for every vertex there is a color that appears exactly once in its open neighborhood. For a graph $G$, the smallest number of colors required for such a coloring is called the conflict-free open neighborhood (CFON) chromatic number and is denoted by $χ_{ON}(G)$. By considering closed neighborhood instead of open neighborhood, we obtain the analogous notions of conflict-free closed neighborhood (CFCN) coloring, and CFCN chromatic number (denoted by $χ_{CN}(G)$). The notion of conflict-free coloring was introduced in 2002, and has since received considerable attention.
In this paper, we study some extremal questions related to CFON and CFCN coloring. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02570 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Extremal Results on Conflict-free Coloring Bhyravarapu, Sriram Gupta, Shiwali Kalyanasundaram, Subrahmanyam Mathew, Rogers Combinatorics Discrete Mathematics 05C15, 68R10 A conflict-free open neighborhood coloring of a graph is an assignment of colors to the vertices such that for every vertex there is a color that appears exactly once in its open neighborhood. For a graph $G$, the smallest number of colors required for such a coloring is called the conflict-free open neighborhood (CFON) chromatic number and is denoted by $χ_{ON}(G)$. By considering closed neighborhood instead of open neighborhood, we obtain the analogous notions of conflict-free closed neighborhood (CFCN) coloring, and CFCN chromatic number (denoted by $χ_{CN}(G)$). The notion of conflict-free coloring was introduced in 2002, and has since received considerable attention. In this paper, we study some extremal questions related to CFON and CFCN coloring. |
| title | Extremal Results on Conflict-free Coloring |
| topic | Combinatorics Discrete Mathematics 05C15, 68R10 |
| url | https://arxiv.org/abs/2305.02570 |