19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details
PDF | XML

Some algorithms on UNO graphs

Presented by Dr. Janja JEREBIC
Type: Oral presentation
Track: General session

Content

UNO is a well-known card game whose relations with graph theory we investigate in this talk. To a set of UNO cards, we attribute an UNO-graph: its vertices correspond to the cards, and two cards are adjacent if and only if they match according to the rules of the game. It is known that a graph G is an UNO-graph if and only if G is a line graph of a bipartite graph. We characterize UNO-graph as claw-free graph G in which any two maximal cliques share at most one vertex, and the graph of maximal cliques of G is bipartite. The new characterization is used in a linear time recognition algorithm. Our results extend to line graphs of bipartite multigraphs, which correspond to the game with several equal cards. This structure also yields linear algorithms for several problems on such graphs, which were before only known to be polynomially solvable.

Place

Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors

More

Co-authors

More