[Algoritmi] Esercizio grafo

[absinth]

Ciao a tutti! Sto facendo un esercizio con la seguente consegna:

Dato un grafo semplice e connesso, con n vertici e m rami, si vogliono colorare i vertici
con due colori diversi (ad esempio, bianco o nero) in modo che non esistano due vertici
adiacenti aventi lo stesso colore.
Non sempre il problema ha soluzione: disegnare un grafo (con n > 2 e m > 2) in cui il
problema ha soluzione e un grafo (con n > 2 e m > 2) in cui il problema non ha soluzione.
Progettare un algoritmo che, in un tempo O(n + m), colora il grafo oppure decide che il
grafo non è colorabile.

Intanto ho inizializzato tutti i vertici incolori e i rami inesplorati.
Ho pensato di farlo con un attraversamento in ampiezza (BFS) verificando ogni volta tra i rami non ancora esplorati di un vertice che dall'altra parte ci sia un vertice che se colorato, con un colore diverso, se incolore - lo coloro io con un colore diverso..Se ciò non vale ritorna dando falso, altrimenti tutto va bene e va fino alla fine dando vero.
Non sono sicuro però che l'algoritmo vada sempre bene. Ci sono per caso grafi strani in cui non vale? In teoria le prestazioni di un BFS sono O(n+m) dove n - numero di vertici mentre m - numero di rami.
Ho scritto un pseudocodice che non è bello da leggere però sintetico. Chiaramente per W = White , B = Black

Iterable vlist = G.Vertex();
Iterable elist = G.Edge();
for each v in vlist
		v.setLabel(COLORLESS);
for each e in elist
		e.setLabel(UNEXPLORED);
//gia speso un tempo theta(n+m)
//Attraversamento di tipo BFS
boolean color(G,v)
		v.setLabel(W) //white
		List[0].insert(v)
		k = 0;
		while(!List[k].isEmpty())
			w = List[k].get()
			for each e in w.edgeList()
				if(e.getLabel()==UNEXPLORED)
					u = w.opposite(e)
					if(u.getLabel()==INCOLOR)
						if (w.getLabel()==W)
							u.setLabel(B)
						else
							u.setLabel(W)
						List[k+1].insert(u)
						e.setLabel(DISCOVERY)
					else
						if(w.getLabel()==u.getLabel())
							return FALSE
						e.setLabel(CROSS)
			k++
		return TRUE		
			

L'ho scritto anche in un modo che forse potrebbe essere più chiaro

[apatriarca]

Non ci ho pensato più di tanto ma dovrebbe essere corretto.

[absinth]

Grazie per la conferma, infatti non trovo altre alternative possibili conoscendo i metodi già studiati