An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929361071898624 |
|---|---|
| author | Char, Arnab Karthick, T. |
| author_facet | Char, Arnab Karthick, T. |
| contents | Given a graph $G$, the parameters $χ(G)$ and $ω(G)$ respectively denote the chromatic number and the clique number of $G$. A function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $f(1) = 1$ and $f(x) \geq x$, for all $x \in \mathbb{N}$ is called a $χ$-binding function for the given class of graphs $\cal{G}$ if every $G \in \cal{G}$ satisfies $χ(G) \leq f(ω(G))$, and the \emph{smallest $χ$-binding function} $f^*$ for $\cal{G}$ is defined as $f^*(x) := \max\{χ(G)\mid G\in {\cal G} \mbox{ and } ω(G)=x\}$. In general, the problem of obtaining the smallest $χ$-binding function for the given class of graphs seems to be extremely hard, and only a few classes of graphs are studied in this direction. In this paper, we study the class of ($P_2+ P_3$, gem)-free graphs, and prove that the function $ϕ:\mathbb{N}\rightarrow \mathbb{N}$ defined by $ϕ(1)=1$, $ϕ(2)=4$, $ϕ(3)=6$ and $ϕ(x)=\left\lceil\frac{1}{4}(5x-1)\right\rceil$, for $x\geq 4$ is the smallest $χ$-binding function for the class of ($P_2+ P_3$, gem)-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_17819 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs Char, Arnab Karthick, T. Combinatorics Discrete Mathematics Given a graph $G$, the parameters $χ(G)$ and $ω(G)$ respectively denote the chromatic number and the clique number of $G$. A function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $f(1) = 1$ and $f(x) \geq x$, for all $x \in \mathbb{N}$ is called a $χ$-binding function for the given class of graphs $\cal{G}$ if every $G \in \cal{G}$ satisfies $χ(G) \leq f(ω(G))$, and the \emph{smallest $χ$-binding function} $f^*$ for $\cal{G}$ is defined as $f^*(x) := \max\{χ(G)\mid G\in {\cal G} \mbox{ and } ω(G)=x\}$. In general, the problem of obtaining the smallest $χ$-binding function for the given class of graphs seems to be extremely hard, and only a few classes of graphs are studied in this direction. In this paper, we study the class of ($P_2+ P_3$, gem)-free graphs, and prove that the function $ϕ:\mathbb{N}\rightarrow \mathbb{N}$ defined by $ϕ(1)=1$, $ϕ(2)=4$, $ϕ(3)=6$ and $ϕ(x)=\left\lceil\frac{1}{4}(5x-1)\right\rceil$, for $x\geq 4$ is the smallest $χ$-binding function for the class of ($P_2+ P_3$, gem)-free graphs. |
| title | An optimal chromatic bound for ($P_2+P_3$, gem)-free graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2405.17819 |