The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Distinguishability of locally finite trees.”

Parity vertex colorings of binomial trees

Petr Gregor, Riste Škrekovski (2012)

Discussiones Mathematicae Graph Theory

Similarity:

We show for every k ≥ 1 that the binomial tree of order 3k has a vertex-coloring with 2k+1 colors such that every path contains some color odd number of times. This disproves a conjecture from [1] asserting that for every tree T the minimal number of colors in a such coloring of T is at least the vertex ranking number of T minus one.

Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

Dariusz Dereniowski (2009)

Discussiones Mathematicae Graph Theory

Similarity:

A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation...