$(2,4)$-Colorability of Planar Graphs Excluding $3$-, $4$-, and $6$-Cycles
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917891308257280 |
|---|---|
| author | Sittitrai, Pongpat Pimpasalee, Wannapol Nakprasit, Kittikorn |
| author_facet | Sittitrai, Pongpat Pimpasalee, Wannapol Nakprasit, Kittikorn |
| contents | A defective $k$-coloring is a coloring on the vertices of a graph using colors $1,2, \dots, k$ such that adjacent vertices may share the same color. A $(d_1,d_2)$-\emph{coloring} of a graph $G$ is a defective $2$-coloring of $G$ such that any vertex colored by color $i$ has at most $d_i$ adjacent vertices of the same color, where $i\in\{1,2\}$. A graph $G$ is said to be $(d_1,d_2)$-\emph{colorable} if it admits a $(d_1,d_2)$-coloring.
Defective $2$-coloring in planar graphs without $3$-cycles, $4$-cycles, and $6$-cycles has been investigated by Dross and Ochem, as well as Sittitrai and Pimpasalee. They showed that such graphs are $(0,6)$-colorable and $(3,3)$-colorable, respectively. In this paper, we proved that these graphs are also $(2,4)$-colorable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07129 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | $(2,4)$-Colorability of Planar Graphs Excluding $3$-, $4$-, and $6$-Cycles Sittitrai, Pongpat Pimpasalee, Wannapol Nakprasit, Kittikorn Combinatorics 05C15 05C10 A defective $k$-coloring is a coloring on the vertices of a graph using colors $1,2, \dots, k$ such that adjacent vertices may share the same color. A $(d_1,d_2)$-\emph{coloring} of a graph $G$ is a defective $2$-coloring of $G$ such that any vertex colored by color $i$ has at most $d_i$ adjacent vertices of the same color, where $i\in\{1,2\}$. A graph $G$ is said to be $(d_1,d_2)$-\emph{colorable} if it admits a $(d_1,d_2)$-coloring. Defective $2$-coloring in planar graphs without $3$-cycles, $4$-cycles, and $6$-cycles has been investigated by Dross and Ochem, as well as Sittitrai and Pimpasalee. They showed that such graphs are $(0,6)$-colorable and $(3,3)$-colorable, respectively. In this paper, we proved that these graphs are also $(2,4)$-colorable. |
| title | $(2,4)$-Colorability of Planar Graphs Excluding $3$-, $4$-, and $6$-Cycles |
| topic | Combinatorics 05C15 05C10 |
| url | https://arxiv.org/abs/2501.07129 |