id: 00089406
dt: j
an: 00089406
au: Hoover, D.N.
ti: Complexity of graph covering problems for graphs of low degree.
so: J. Comb. Math. Comb. Comput. 11, 187-208 (1992).
py: 1992
pu: Charles Babbage Research Centre, Winnipeg
la: EN
cc:
ut: graph covering problems; low degree; cliques; cover; NP-complete
ci:
li:
ab: The author considers three related problems on graphs: (1) What is the
smallest number of cliques into which the edges of a graph can be
partitioned? (2) How many cliques are needed to cover the edges of a
graph? (3) Can the edges of a graph be partitioned into maximal
cliques? All three problems are known to be NP-complete for general
graphs. If $Δ(G)$ is the largest degree of a graph $G$, the author
shows that (1) is NP-complete for $Δ(G)\ge 5$ and polynomial for
$Δ(G)\le 4$; (2) is NP-complete for $Δ(G)\ge 6$ and polynomial for
$Δ(G)\le 5$; (3) is NP-complete for $Δ(G)\ge 8$ and polynomial for
$Δ(G)\le 7$.
rv: P.Jaillet (Austin)