Barát, János (2019) Decomposition of cubic graphs related to Wegner’s conjecture. DISCRETE MATHEMATICS, 342 (5). pp. 1520-1527. ISSN 0012-365X
|
Text
1901.pdf Available under License Creative Commons Attribution. Download (155kB) | Preview |
Official URL: http://doi.org/10.1016/j.disc.2019.01.025
Abstract
Thomassen formulated the following conjecture: Every 3-connected cubic graph has a red-blue vertex coloring such that the blue subgraph has maximum degree 1 (that is, it consists of a matching and some isolated vertices) and the red subgraph has minimum degree at least 1 and contains no 3-edge path. We prove the conjecture for Generalized Petersen graphs. We indicate that a coloring with the same properties might exist for any subcubic graph. We confirm this statement for all subcubic trees.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 21 Nov 2019 15:21 |
| Last Modified: | 20 Apr 2023 11:32 |
| URI: | http://real.mtak.hu/id/eprint/103553 |
Actions (login required)
 |
Edit Item |
