3-Coloring $P_t$-Free Graphs With Only One Prescribed Induced Odd Cycle Length
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917130959585280 |
|---|---|
| author | Zhou, Yidong Zhong, Mingxian Huang, Shenwei |
| author_facet | Zhou, Yidong Zhong, Mingxian Huang, Shenwei |
| contents | A graph is $P_t$-free if it contains no induced subgraph isomorphic to a $t$-vertex path. A graph is not bipartite if and only if it contains an induced subgraph isomorphic to a $k$-vertex cycle, where $k$ is odd. We focus on the 3-coloring problem for $P_t$-free graphs that have only one prescribed induced odd cycle length. For any integer $t$ and any odd integer $k$, let $\mathcal{G}_{t,k}$ be the class of graphs that are $P_{t}$-free and all their induced odd cycles must be $C_k$. In this paper, we present a polynomial-time algorithm that solves the 3-coloring problem for any graph in $\mathcal{G}_{10,7}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_06367 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | 3-Coloring $P_t$-Free Graphs With Only One Prescribed Induced Odd Cycle Length Zhou, Yidong Zhong, Mingxian Huang, Shenwei Combinatorics A graph is $P_t$-free if it contains no induced subgraph isomorphic to a $t$-vertex path. A graph is not bipartite if and only if it contains an induced subgraph isomorphic to a $k$-vertex cycle, where $k$ is odd. We focus on the 3-coloring problem for $P_t$-free graphs that have only one prescribed induced odd cycle length. For any integer $t$ and any odd integer $k$, let $\mathcal{G}_{t,k}$ be the class of graphs that are $P_{t}$-free and all their induced odd cycles must be $C_k$. In this paper, we present a polynomial-time algorithm that solves the 3-coloring problem for any graph in $\mathcal{G}_{10,7}$. |
| title | 3-Coloring $P_t$-Free Graphs With Only One Prescribed Induced Odd Cycle Length |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.06367 |