Coloring three graph classes with Δ - 1 colors
- 4 November 2025
- journal article
- Published by World Scientific Pub Co Pte Ltd in Discrete Mathematics, Algorithms and Applications
Abstract
The Borodin-Kostochka conjecture states that every connected graph [ ] with [ ] satisfies [ ]. In this paper, we verify this conjecture for any [ ]-free graph [ ] (where a [ ] is a [ ] with a pendant edge), by further prohibiting induced subgraph HVN (where a [ ] is a [ ] together with one more vertex which is adjacent to exactly two vertices of [ ]), we verify this conjecture with [ ]. Furthermore, for any [ ]-free graph [ ] (where a [ ] is a [ ] with a pendant edge), we verify this conjecture with [ ].Keywords
Funding Information
- Yangzhou Innovation Capability Enhancement Fund (YZ2024245)