Displaying similar documents to “Extreme distances in multicolored point sets.”

On-line Ramsey theory for bounded degree graphs.

Butterfield, Jane, Grauman, Tracy, Kinnersley, William B., Milans, Kevin G., Stocker, Christopher, West, Douglas B. (2011)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks

Piotr Formanowicz, Krzysztof Tanaś (2012)

International Journal of Applied Mathematics and Computer Science

Similarity:

It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks....

A decomposition of gallai multigraphs

Alexander Halperin, Colton Magnant, Kyle Pula (2014)

Discussiones Mathematicae Graph Theory

Similarity:

An edge-colored cycle is rainbow if its edges are colored with distinct colors. A Gallai (multi)graph is a simple, complete, edge-colored (multi)graph lacking rainbow triangles. As has been previously shown for Gallai graphs, we show that Gallai multigraphs admit a simple iterative construction. We then use this structure to prove Ramsey-type results within Gallai colorings. Moreover, we show that Gallai multigraphs give rise to a surprising and highly structured decomposition into directed...

Spanning trees with many or few colors in edge-colored graphs

Hajo Broersma, Xueliang Li (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard. ...

Locally bounded -colorings of trees

C. Bentz, C. Picouleau (2009)

RAIRO - Operations Research

Similarity:

Given a tree with vertices, we show, by using a dynamic programming approach, that the problem of finding a 3-coloring of respecting local (, associated with prespecified subsets of vertices) color bounds can be solved in log) time. We also show that our algorithm can be adapted to the case of -colorings for fixed .

Total edge irregularity strength of trees

Jaroslav Ivančo, Stanislav Jendrol' (2006)

Discussiones Mathematicae Graph Theory

Similarity:

A total edge-irregular k-labelling ξ:V(G)∪ E(G) → {1,2,...,k} of a graph G is a labelling of vertices and edges of G in such a way that for any different edges e and f their weights wt(e) and wt(f) are distinct. The weight wt(e) of an edge e = xy is the sum of the labels of vertices x and y and the label of the edge e. The minimum k for which a graph G has a total edge-irregular k-labelling is called the total edge irregularity strength of G, tes(G). In this paper we prove that...