Will pci express video card work on p4c800-e asus mother board

According to the specs of the P4C800-E deluxe motherboard it has one AGP and 5 PCI slots. You can only place a PCI (not PCI-E) or an AGP card into your computer, AGP is better/faster than PCI cards.

The best graphics card you can place into your computer is the HD3850 AGP card. It will mostlikely be bottlenecked by your CPU, so overclocking will give you more performance.
http://www.newegg.com/Product/Product.aspx?Item=N82E168...
You mostlikely will need to upgrade your PSU to 450watts in order to use this card.

Also if you are looking to upgrade both the PSU and graphics card you might as well look into upgrading the whole system to a new one, as it will give you better performance for the amount you will spend.

The 4670 should be as fast as the 3850, but with better power/thermal numbers. If you have a slower clocked P4 or a single core (anything other then the P4D) then I'd get the 4650. Not a bad card, shouldn't cost to much, and probably won't need a new PSU either.