Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913237515108352 |
|---|---|
| author | Alecu, Bogdan Kanté, Mamadou Moustapha Lozin, Vadim Zamaraev, Viktor |
| author_facet | Alecu, Bogdan Kanté, Mamadou Moustapha Lozin, Vadim Zamaraev, Viktor |
| contents | Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies that any hereditary class of graphs of bounded lettericity can be described by finitely many forbidden induced subgraphs. This, in turn, implies, in a non-constructive way, polynomial-time recognition of such classes. However, no constructive algorithms and no specific bounds on the size of forbidden graphs are available up to date. In the present paper, we develop an algorithm that recognizes $n$-vertex graphs of lettericity at most $k$ in time $f(k)n^3$ and show that any minimal graph of lettericity more than $k$ has at most $2^{O(k^2\log k)}$ vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12559 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions Alecu, Bogdan Kanté, Mamadou Moustapha Lozin, Vadim Zamaraev, Viktor Combinatorics Discrete Mathematics Data Structures and Algorithms Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies that any hereditary class of graphs of bounded lettericity can be described by finitely many forbidden induced subgraphs. This, in turn, implies, in a non-constructive way, polynomial-time recognition of such classes. However, no constructive algorithms and no specific bounds on the size of forbidden graphs are available up to date. In the present paper, we develop an algorithm that recognizes $n$-vertex graphs of lettericity at most $k$ in time $f(k)n^3$ and show that any minimal graph of lettericity more than $k$ has at most $2^{O(k^2\log k)}$ vertices. |
| title | Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.12559 |