On the finiteness of $k$-vertex-critical $2P_2$-free graphs with forbidden induced squids or bulls
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_ | 1866916138362863616 |
|---|---|
| author | Adekanye, Melvin Bury, Christopher Cameron, Ben Knodel, Thaler |
| author_facet | Adekanye, Melvin Bury, Christopher Cameron, Ben Knodel, Thaler |
| contents | A graph is $k$-vertex-critical if $χ(G)=k$ but $χ(G-v)<k$ for all $v\in V(G)$ and $(G,H)$-free if it contains no induced subgraph isomorphic to $G$ or $H$. We show that there are only finitely many $k$-vertex-critical $(2P_2,H)$-free graphs for all $k$ when $H$ is isomorphic to any of the following graphs of order $5$: $bull$, $chair$, $claw+P_1$, or $\overline{diamond+P_1}$.
The latter three are corollaries of more general results where $H$ is isomorphic to $(m, \ell)$-$squid$ for $m=3,4$ and any $\ell\ge 1$ where an $(m,\ell)$-$squid$ is the graph obtained from an $m$-cycle by attaching $\ell$ leaves to a single vertex of the cycle. For each of the graphs $H$ above and any fixed $k$, our results imply the existence of polynomial-time certifying algorithms for deciding the $k$-colourability problem for $(2P_2,H)$-free graphs. Further, our structural classifications allow us to exhaustively generate, with aid of computer search, all $k$-vertex-critical $(2P_2,H)$-free graphs for $k\le 7$ when $H=bull$ or $H=(4,1)$-$squid$ (also known as $banner$). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_15908 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the finiteness of $k$-vertex-critical $2P_2$-free graphs with forbidden induced squids or bulls Adekanye, Melvin Bury, Christopher Cameron, Ben Knodel, Thaler Combinatorics Discrete Mathematics A graph is $k$-vertex-critical if $χ(G)=k$ but $χ(G-v)<k$ for all $v\in V(G)$ and $(G,H)$-free if it contains no induced subgraph isomorphic to $G$ or $H$. We show that there are only finitely many $k$-vertex-critical $(2P_2,H)$-free graphs for all $k$ when $H$ is isomorphic to any of the following graphs of order $5$: $bull$, $chair$, $claw+P_1$, or $\overline{diamond+P_1}$. The latter three are corollaries of more general results where $H$ is isomorphic to $(m, \ell)$-$squid$ for $m=3,4$ and any $\ell\ge 1$ where an $(m,\ell)$-$squid$ is the graph obtained from an $m$-cycle by attaching $\ell$ leaves to a single vertex of the cycle. For each of the graphs $H$ above and any fixed $k$, our results imply the existence of polynomial-time certifying algorithms for deciding the $k$-colourability problem for $(2P_2,H)$-free graphs. Further, our structural classifications allow us to exhaustively generate, with aid of computer search, all $k$-vertex-critical $(2P_2,H)$-free graphs for $k\le 7$ when $H=bull$ or $H=(4,1)$-$squid$ (also known as $banner$). |
| title | On the finiteness of $k$-vertex-critical $2P_2$-free graphs with forbidden induced squids or bulls |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2402.15908 |