A subquadratic certification scheme for P5-free graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913677715701760 |
|---|---|
| author | Bousquet, Nicolas Zeitoun, Sébastien |
| author_facet | Bousquet, Nicolas Zeitoun, Sébastien |
| contents | In local certification, vertices of a $n$-vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to certificates, which are pieces of information that are given to the vertices. In this work, we focus on the local certification of $P_5$-freeness, and we prove a $O(n^{3/2})$ upper bound on the size of the certificates, which is (to our knowledge) the first subquadratic upper bound for this property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_14658 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A subquadratic certification scheme for P5-free graphs Bousquet, Nicolas Zeitoun, Sébastien Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms In local certification, vertices of a $n$-vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to certificates, which are pieces of information that are given to the vertices. In this work, we focus on the local certification of $P_5$-freeness, and we prove a $O(n^{3/2})$ upper bound on the size of the certificates, which is (to our knowledge) the first subquadratic upper bound for this property. |
| title | A subquadratic certification scheme for P5-free graphs |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.14658 |