The bounded-degree tag has no wiki summary.
12
votes
4answers
493 views
hardness of approximating the chromatic number in graphs with bounded degree
I am looking for hardness results on vertex coloring of graphs with bounded degree.
Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
3
votes
1answer
123 views
bounded outdegree bipartite spanners
Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :
$G'$ ...
15
votes
2answers
288 views
Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?
Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover.
The Wikipedia article says that it is poly-time ...
-1
votes
2answers
177 views
Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G
You are given two graphs G and H , and want to know if H is a subgraph of G.
You know that H has a max vertex degree K (constant integer).
What can you say about the complexity of this?
I know that ...
10
votes
1answer
229 views
Hardness of approximating fractional chromatic number on bounded degree graphs
Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
