Back to Search
Start Over
On 3-degree 4-chordal graphs.
- Source :
- Discrete Mathematics, Algorithms & Applications; Jan2023, Vol. 15 Issue 1, p1-23, 23p
- Publication Year :
- 2023
-
Abstract
- A graph G is a 3-degree 4-chordal graph if every cycle of length at least five has a chord and the degree of each vertex is at most three. In this paper, we investigate the structure of 3-degree 4-chordal graphs, which is a subclass of 3-degree graphs. We present a structural characterization based on minimal vertex separators and bi-connected components. Many classical problems are known to be NP-complete for 3-degree graphs, and 3-degree 4-chordal graphs are a nontrivial subclass of 3-degree graphs. Using our structural results, we present polynomial-time algorithms for many classical problems which are grouped into (i) subset problems (vertex cover and its variants, feedback vertex set, Steiner tree), (ii) Hamiltonicity and its variants, (iii) graph embedding problems (treewidth, minimum fill-in), and (iv) Coloring problems(rainbow coloring). [ABSTRACT FROM AUTHOR]
- Subjects :
- RAINBOWS
GRAPH coloring
BIPARTITE graphs
ALGORITHMS
TREES
Subjects
Details
- Language :
- English
- ISSN :
- 17938309
- Volume :
- 15
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Discrete Mathematics, Algorithms & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 161657289
- Full Text :
- https://doi.org/10.1142/S1793830922500537