ROMEO RIZZI,
On the Recognition of P4-Indifferent Graphs,
submitted descrizione:
Un grafo é
P4-indifferent
se ammette un ordinamento dei nodi
tale che per ogni cammino indotto
da quattro nodi a,b,c,dsi ha che a<b<c<doppure che a>b>c>d.
La famiglia dei grafi P4-indifferent
include quella degli indifferent
ed inoltre ogni grafo che sia P4-indifferent
é perfectly orderable.
L'interesse per grafi perfectly orderable
é motivato dall'osservazione di Chvátal
che un semplice algoritmo greedy
lungo l'ordinamento
produce sempre una colorazione ottima dei nodi.
Tuttavia il riconoscimento di grafi perfectly orderable
in generale é NP-completo.
Recentemente, Hoàng, Maffray e Noy
avevano dato una caratterizzazione dei grafi P4-indifferent
in termini di sottografi indotti proibiti.
Noi riorganizziamo la loro dimostrazione
e ne deriviamo un algoritmo lineare per il riconoscimento
di grafi P4-indifferent.
Se il grafo in input é P4-indifferent,
allora l'algoritmo produce inoltre un ordinamento <come le proprietá di cui sopra.
