Home » Keyword index

tournament


Graph Theory » Graph Algorithms

PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

Question   Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Keywords: feedback arc set; PTAS; tournament

Posted by fhavet
updated March 15th, 2013
add new comment
Graph Theory » Directed Graphs » Tournaments

Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is rainbow if all its edges have distinct colors, and monochromatic if all its edges have the same color.

Problem   Let $ G $ be a tournament with edges colored from a set of three colors. Is it true that $ G $ must have either a rainbow directed cycle of length three or a vertex $ v $ so that every other vertex can be reached from $ v $ by a monochromatic (directed) path?

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 15th, 2008
add new comment
Graph Theory » Directed Graphs » Tournaments

Monochromatic reachability in edge-colored tournaments ★★★

Author(s): Erdos

Problem   For every $ n $, is there a (least) positive integer $ f(n) $ so that whenever a tournament has its edges colored with $ n $ colors, there exists a set $ S $ of at most $ f(n) $ vertices so that every vertex has a monochromatic path to some point in $ S $?

Keywords: digraph; edge-coloring; tournament

Posted by mdevos
updated July 9th, 2008
add new comment
Syndicate content