On graphs double-critical with respect to the colouring number
The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2015-09-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2129/pdf |
| _version_ | 1797270090310221824 |
|---|---|
| author | Matthias Kriesell Anders Pedersen |
| author_facet | Matthias Kriesell Anders Pedersen |
| author_sort | Matthias Kriesell |
| collection | DOAJ |
| description | The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph $G$ is said to be <i>double</i>-col-<i>critical</i> if the colouring number of $G-V(e)$ is at most the colouring number of $G$ minus 2. A connected graph G is said to be double-col-critical if each edge of $G$ is double-col-critical. We characterise the <i>double</i>-col-<i>critical</i> graphs with colouring number at most 5. In addition, we prove that every 4-col-critical non-complete graph has at most half of its edges being double-col-critical, and that the extremal graphs are precisely the odd wheels on at least six vertices. We observe that for any integer $k$ greater than 4 and any positive number $ε$, there is a $k$-col-critical graph with the ratio of double-col-critical edges between $1- ε$ and 1. |
| first_indexed | 2024-04-25T01:58:44Z |
| format | Article |
| id | doaj.art-9ead05260ccd45dab4c3561c0d95d4c2 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:44Z |
| publishDate | 2015-09-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-9ead05260ccd45dab4c3561c0d95d4c22024-03-07T15:28:21ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502015-09-01Vol. 17 no.2Graph Theory10.46298/dmtcs.21292129On graphs double-critical with respect to the colouring numberMatthias Kriesell0Anders Pedersen1Institute of Mathematics - Technical University of IlmenauDepartment of Mathematics and Computer Science [Odense]The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph $G$ is said to be <i>double</i>-col-<i>critical</i> if the colouring number of $G-V(e)$ is at most the colouring number of $G$ minus 2. A connected graph G is said to be double-col-critical if each edge of $G$ is double-col-critical. We characterise the <i>double</i>-col-<i>critical</i> graphs with colouring number at most 5. In addition, we prove that every 4-col-critical non-complete graph has at most half of its edges being double-col-critical, and that the extremal graphs are precisely the odd wheels on at least six vertices. We observe that for any integer $k$ greater than 4 and any positive number $ε$, there is a $k$-col-critical graph with the ratio of double-col-critical edges between $1- ε$ and 1.https://dmtcs.episciences.org/2129/pdfgraph characterizationsgraph colouringdegenerate graphscolouring numberdouble-critical graphs[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Matthias Kriesell Anders Pedersen On graphs double-critical with respect to the colouring number Discrete Mathematics & Theoretical Computer Science graph characterizations graph colouring degenerate graphs colouring number double-critical graphs [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | On graphs double-critical with respect to the colouring number |
| title_full | On graphs double-critical with respect to the colouring number |
| title_fullStr | On graphs double-critical with respect to the colouring number |
| title_full_unstemmed | On graphs double-critical with respect to the colouring number |
| title_short | On graphs double-critical with respect to the colouring number |
| title_sort | on graphs double critical with respect to the colouring number |
| topic | graph characterizations graph colouring degenerate graphs colouring number double-critical graphs [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2129/pdf |
| work_keys_str_mv | AT matthiaskriesell ongraphsdoublecriticalwithrespecttothecolouringnumber AT anderspedersen ongraphsdoublecriticalwithrespecttothecolouringnumber |