Laurent Koscielny bundled home his first Arsenal goal after 24 minutes but then produced a poor back header that allowed Bolton to equalise just before half-time through Johan Elmander.
Marouane Chamakh headed the hosts back in front and the game swung further away when Gary Cahill was sent off for a tackle from behind on the Moroccan.
Alex Song netted Arsenal's 1,000th Premier League goal under Arsene Wenger and substitute Carlos Vela stroked in number four with seven minutes left.
As expected, the home side made all the early running, with captain Cesc Fabregas, who has a fine personal record against Bolton, having a shot blocked after cutting into the right side of the area.
Andrey Arshavin should have made it 1-0 after latching onto a brilliant through ball by Tomas Rosicky, but Bolton goalkeeper Adam Bogdan - making his first Premier League start in place of the suspended Jussi Jaaskelainen - was out quickly to close the Russian down at the edge of the penalty area.
Rosicky then had a go himself, driving an angled shot just over as Arsenal continued to press.
Bolton found an opening on 12 minutes when a knockdown by former Gunner Fabrice Muamba fell to Kevin Davies, but the striker's shot on the turn was held by Manuel Almunia.
The Gunners moved ahead 12 minutes later.
Jack Wilshere's angled chip across the penalty area picked out Fabregas' run at the far post, and his cutback was bundled in by Koscielny despite the best efforts of Bogdan.
The Hungarian was being kept busy, as a fine passing move ended with Rosicky drilling in a low, angled shot which produced another fine reaction block from the youngster.
Arshavin clipped the side-netting after getting ahead of Zat Knight before he was again denied on the breakaway, as this time Gretar Steinsson did just enough to put the Russian off balance.
Bolton then snatched an equaliser just before half-time following a terrible mix up in the Arsenal defence.
Koscielny's backward header was far too soft, leaving Almunia exposed as Lee Chung-yong darted onto the loose ball.
The Korean rounded the goalkeeper before chipping back across goal, where Elmander headed in at the far post.
The tempo was lacklustre during the opening exchanges of the second half, as both sides knew the next goal would be crucial.
Song hacked away a loose ball in the Arsenal six-yard box before Chamakh burst clear and on to the edge of the Bolton box, but again Bogdan produced a superb save.
However, there was little he could do moments later, as the danger was not cleared after the resulting corner, Chamakh headed in Fabregas' cross at the far post to restore Arsenal's lead after 58 minutes.
Koscielny and Davis, jumping in at full pelt, both needed treatment after a nasty clash of heads as they challenged for a ball on the edge of the Arsenal penalty area.
Despite calls for action from referee Attwell, it was Emmanuel Eboue who ended up in the book for protesting.
The Nuneaton official - who famously allowed a "ghost goal" during a match between Watford and Reading two years ago - then missed what looked liked a foul by Kieran Gibbs on Lee at the edge of the Arsenal box.
Play continued upfield and the 27-year-old official soon did reach for his back pocket, to show Cahill a straight red card after his tackle from behind on Chamakh.
The match suddenly developed an edge, as a few hefty challenges went in from both sides, Arsenal substitute Abou Diaby eventually having to be replaced after suffering an injury in a clash with Paul Robinson.
Song made it 3-1 when he collected a cutback from Arshavin to cleverly chip the goalkeeper from a tight angle, before substitute Vela stroked in number four with seven minutes left - and Eboue was denied what looked a penalty when tripped by Muamba.