KIEV, Aug. 31 – Ukrainian forces and residents in Ukraine's eastern port of Mariupol braced for attack on Sunday from advancing pro-Russian rebels who Kiev says are backed by a Russian armored column.

Pro-Russian separatists and Ukrainian troops both used bulldozers to dig trenches on Sunday along the new front, a 40-km strip of coastal highway on the Sea of Azov, with battle looming for a city of half a million people.

The developments come as Russian President Vladimir Putin called on Sunday for immediate talks on the "statehood" of southern and eastern Ukraine, Reuters reported.

The Kremlin leader's remarks, two days after a public appearance in which he compared the Kiev government with Nazis and warned the West not to "mess with us", came as Europe and the United States prepared possible further sanctions to halt what they say is direct Russian military involvement in the war in Ukraine.

Germany aired suspicions that Moscow might be trying to create a land corridor to supply Crimea, which it annexed from Ukraine in March, while the four-month conflict moved onto the sea for the first time on Sunday.

The separatists said they had fired on a Ukrainian vessel in the Azov Sea using land-based artillery, Kiev says Moscow's forces have come to the aid of pro-Russian insurgents, tipping the military balance in the rebels' favor.

Talks should be held immediately "and not just on technical issues but on the political organization of society and statehood in southeastern Ukraine", Putin said in an interview with Channel 1 state television, his hair tousled by wind on the shore of a lake.

Putin's use of the word "statehood" was interpreted in Western media as implying backing for the rebel demand of independence, something Moscow has so far stopped short of publicly endorsing.

However, Putin's spokesman Dmitry Peskov said there was no new endorsement from Moscow for rebel independence.

Asked if "New Russia", a term pro-Moscow rebels use for their territory, should still be part of Ukraine, Peskov said: "Of course."

The deputy leader of the rebel Donetsk People's Republic, Andrei Purgin, said he was due to participate in talks in the Belarus capital Minsk on Monday. Past talks by a "contact group" involving Moscow, Kiev and the rebels have covered technical issues such as access to the crash site of a Malaysian airliner shot down in July, but not political questions.

The past week has seen Ukrainian forces flee in the path of a new rebel advance, drawing concern from Ukraine's Western allies, who say armored columns of Russian troops came to the aid of a rebellion that would otherwise have been near collapse.

European Union leaders agreed on Saturday to draw up new economic sanctions against Moscow, a move hailed by the United States, which is planning tighter sanctions of its own and wants to act jointly with Europe.

German Foreign Minister Frank-Walter Steinmeier saw a possible link between the fighting around Mariupol and the Crimean peninsula, which is under Moscow's control but has no land border with Russia.

"It doesn't appear to be ruled out that Russia is trying to make land connections to organize supplies for the population of Crimea," he was quoted by the Maerkische Allgemeine newspaper as saying in an interview. "Russian land bridges and corridors would be just as illegal and deplorable as its annexation of Crimea."

Some residents of Mariupol have taken to the streets of the port to show support for the Ukrainian government as pro-Russian forces gain ground. Many others have fled from the prospect of an all-out assault on the city of nearly 500,000 people.

"We are proud to be from this city and we are ready to defend it from the occupiers," said Alexandra, 28, a post office clerk wearing a ribbon in blue and yellow Ukrainian colors.

"We will dig trenches. We will throw petrol bombs at them, the occupiers," she said. "I believe our army and our (volunteer) battalions will protect us."

Kiev and its allies in Europe and the United States say the new rebel offensive has been backed by more than 1,000 Russian troops fighting openly to support the insurgents. The rebels themselves say thousands of Russian troops have fought on their behalf while "on leave.”

Reuters journalists on the Russian side of the border have seen Russian troops showing signs of having returned from battle, with their insignia removed or rubbed out.

Despite the evidence, Moscow denies its troops are fighting in Ukraine and says a small party of soldiers crossed the border by accident. Russian Major-General Alexei Ragozin said the paratroops were handed back after "very difficult" negotiations. (rt/ez)