ORDER AND JUDGMENT*

Petitioner-appellant Timothy Duncan appeals the district court's order dismissing his petition for a writ of habeas corpus on the ground that he failed to exhaust state post-conviction remedies. Also before this court is the question of whether we should grant Mr. Duncan a certificate of appealability. We exercise jurisdiction pursuant to 28 U.S.C. § 1291, grant Mr. Duncan a certificate of appealability, and reverse and remand this case to the district court.

Mr. Duncan was convicted on two counts of armed robbery in a New Mexico state court and is serving a thirty-four year sentence. Mr. Duncan appealed his conviction to the New Mexico Court of Appeals arguing, among other things, that his due process rights were violated because the prosecutor vindictively sought to enhance his sentence in his second trial after he successfully appealed the exclusion of defense evidence from his first trial. The state court of appeals affirmed, and the New Mexico Supreme Court subsequently denied Mr. Duncan's petition for a writ of certiorari. Mr. Duncan then filed the present 28 U.S.C. § 2254 petition in federal court, raising the prosecutorial vindictiveness claim presented on direct appeal. Prior to pursuing federal habeas relief, however, Mr. Duncan did not pursue the state post-conviction remedies available to him. The petition was referred to a magistrate judge, who recommended that the district court dismiss Mr. Duncan's petition because he had not exhausted his state post-conviction remedies as required pursuant to 28 U.S.C. § 2254(c). The district court adopted the magistrate judge's recommendation and dismissed Mr. Duncan's petition without prejudice. Subsequently, the district court denied Mr. Duncan's application for a certificate of probable cause to pursue this appeal.

As a preliminary matter, we must decide whether to issue Mr. Duncan a certificate of appealability. Section 102 of the Antiterrorism and Effective Death Penalty Act (AEDPA) of 1996 requires state habeas petitioners to obtain certificates of appealability prior to seeking appellate review of final orders in habeas proceedings. Pub.L. 104-132, 110 Stat. 1217-18 (codified at 28 U.S.C. § 2253). This court has held that the amended § 2253 applies retroactively to appeals filed prior to the passage of the AEDPA on April 24, 1996, as is the case here. See Lennox v. Evans, 87 F.3d 431, 434 (10th Cir.1996), cert. denied, 117 S. Ct. 746 (1997). A habeas petitioner is entitled to a certificate of appealability only if the petitioner has made a "substantial showing of the denial of a constitutional right." 28 U.S.C. § 2553(c)(2)(1994). We have previously recognized that the standard for granting a certificate of appealability under the AEDPA is the same as the standard set out by the Supreme Court in Barefoot v. Estelle, 463 U.S. 880 (1983). See Lennox, 87 F.3d at 434. Under the Barefoot standard, a certificate will issue only where the petitioner has demonstrated that the issues raised are debatable among jurists of reason, a court could resolve the issues differently, or the questions presented are deserving of further proceedings. 463 U.S. at 893 n. 4.

In his habeas petition and appellate briefs, Mr. Duncan characterizes his habeas claim as a "vindictive prosecution" claim. While, as the defendant points out, Mr. Duncan does not clearly articulate the constitutional right on which his prosecutorial vindictiveness claim is based, he does assert that this claim is identical to his vindictive prosecution claim on direct appeal--which alleged a violation of his due process right under the United States Constitution. Given that Mr. Duncan alludes to the violation of a federal constitutional right in his petition and appellate briefs, and our conclusion below that Mr. Duncan is correct that the district court erred in dismissing his petition for failure to exhaust his state post-conviction remedies, we grant him a certificate of appealability.

II. Exhaustion of State Post-Conviction Remedies

The magistrate judge's findings and recommendations, which were adopted by the district court, recommended dismissal of Mr. Duncan's habeas petition because of his failure to exhaust state post-conviction remedies. Mr. Duncan does not dispute that he did not pursue state post-conviction relief prior to filing the present habeas action. Rather, Mr. Duncan argues that the Supreme Court's interpretation of the 28 U.S.C. § 2254(c) exhaustion requirement makes clear that if the issue on habeas is the same as that presented on direct appeal, there is no need to exhaust state post-conviction remedies prior to seeking habeas relief.

Section 2254(b) of the habeas statute requires that a habeas petitioner in state custody exhaust his or her available state court remedies prior to seeking habeas relief.1 In applying this state exhaustion requirement, § 2254(c) provides that "[a]n applicant shall not be deemed to have exhausted the remedies available in the courts of the State, within the meaning of this section, if he has the right under the law of the State to raise, by any available procedure, the question presented." 28 U.S.C. § 2254(c). While the plain meaning of the section appears rather straightforward, the Supreme Court has applied a judicial exception to this language. The exception allows a petitioner to avoid state post-conviction collateral review where a state court has had the opportunity to rule on the substance of the federal claim. In explaining this provision, the Court has stated:

Read narrowly, [the] language [of § 2254(c) ] appears to preclude a finding of exhaustion if there exists any possibility of further state-court review. We have, however, expressly rejected such a construction, Brown v. Allen, 344 U.S. 443, 448-49, n. 3 (1953), holding instead that once the state courts have ruled upon a claim, it is not necessary for a petition "to ask the state for collateral relief, based upon the same evidence and issues already decided by direct review." Id. at 447. This interpretation reconciles § 2254(c) with § 2254(b), which provides that federal habeas review will lie where state corrective processes are "ineffective to protect the rights of the prisoner." It would be inconsistent with the latter provision, as well as with underlying principles of comity, to mandate recourse to state collateral review whose results have effectively been predetermined, or permanently to bar from federal habeas prisoners in States whose post-conviction procedures are technically inexhaustible.

Castille v. Peoples, 489 U.S. 346, 350 (1989).

Applying the above exception, it is clear that the magistrate judge's recommendation, on which the district court's order is based, is incorrect. The magistrate judge recommended dismissal solely because Mr. Duncan had state post-conviction appeals available to him and had not exhausted them. The magistrate and district judges did not discuss in any manner the exception created by the Court or analyze whether it should be applied in this case. Such a ruling is not justified under the applicable law. However, before reversing the district court's order dismissing Mr. Duncan's petition, we must first examine whether the New Mexico state courts had the opportunity to rule on the substance of the federal claim presented in Mr. Duncan's habeas petition.

To demonstrate compliance with the state exhaustion requirement, a habeas applicant must show that "the substance of a federal habeas corpus claim must first be presented to the state courts." Picard v. Connor, 404 U.S. 270, 278 (1971); see also, Nichols v. Sullivan, 867 F.2d 1250, 1252 (10th Cir.1989). Presentation of a claim's "substance" does not require the defendant to cite " 'book and verse on the federal constitution.' " Picard, 404 U.S. at 278 (quoting Daugherty v. Gladden, 257 F.2d 750, 758 (9th Cir.1958)). Rather, it is only necessary that the federal claim be "fairly presented" to the state courts so that they have the first opportunity to hear the claim sought to be vindicated by the federal habeas petition. Id. at 275. "Although the Supreme Court has interpreted the 'fair presentation' standard as requiring more than that 'all the facts necessary to support the federal claim were before the state courts, ... or that a somewhat similar state-law claim was made,' the language of Picard makes clear that a failure to invoke talismanic language ... should not be the basis for a finding of nonexhaustion." Nichols, 867 F.2d at 1251 (citations omitted).

In this case, Mr. Duncan "fairly presented" the substance of his prosecutorial vindictiveness claim as a federal constitutional claim before the state courts. His direct appeal challenged the prosecutor's actions as a violation of his due process rights under federal constitutional standards. See Rec. vol. I, doc. 15, ex. C at 10-17 (Docketing Statement of Defendant-Appellant dated August 5, 1992) and ex. H at 24-25 (Defendant's Brief In Chief dated June 30, 1993). Mr. Barreras himself admits that Mr. Duncan presented this claim as a federal constitutional claim in the New Mexico courts. See Aple's Br. at 9 ("Petitioner's brief in chief in the New Mexico Court of Appeals and his certiori petition in the New Mexico Supreme Court both referred to specific provisions of the federal Constitution, and both contained discussions of numerous United States Supreme Court and Circuit Court of Appeals [sic] cases."). Furthermore, the New Mexico Court of Appeals, in denying Mr. Duncan's appeal, fully analyzed his prosecutorial vindictiveness claim as a due process violation under the federal constitutional standards set forth by the United States Supreme Court. See Rec. vol. I, doc. 15, ex. J at 2-8 (New Mexico v. Duncan, No. 13,981 (N.M.App.1994). Thus, Mr. Duncan clearly presented the "legal" substance of his federal claim to the New Mexico courts.

However, the "fair presentation" test also requires that the state court has had an opportunity to rule on the claim in light of the full factual record in the case. See Jones v. Hess, 681 F.2d 688, 694 (10th Cir.1982). This court held in Jones that "where a federal habeas petitioner presents newly discovered evidence or other evidence not before the state courts such as to place the case in a significantly different posture, the state courts must be given an opportunity to consider the evidence." Id. We also held, however, that mere "bits of evidence" that were not before the state courts will not render a petitioner's claim unexhausted. Id. At this point in the habeas process we have no reason to believe that Mr. Duncan seeks to introduce new evidence in support of his prosecutorial vindictiveness claim. His habeas petition relies solely on the state trial record, and he has not sought a federal evidentiary hearing. Thus, we conclude on the record before us that Mr. Duncan has exhausted his state remedies in accordance with 28 U.S.C. § 2254(c) by "fairly presenting" the substance of his federal habeas claim to the New Mexico state courts on his direct appeal.2

For the foregoing reasons, we grant Mr. Duncan a certificate of appealability and reverse the district court's order dismissing his petition for failure to exhaust his state post-conviction remedies. We remand this case to the district court for further proceedings. The mandate shall issue forthwith.