All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 64 Next

Displaying 1261 – 1280 of 1341

Showing per page

On-line models and algorithms for max independent set

Bruno Escoffier, Vangelis Th. Paschos (2006)

RAIRO - Operations Research

In on-line computation, the instance of the problem dealt is not entirely known from the beginning of the solution process, but it is revealed step-by-step. In this paper we deal with on-line independent set. On-line models studied until now for this problem suppose that the input graph is initially empty and revealed either vertex-by-vertex, or cluster-by-cluster. Here we present a new on-line model quite different to the ones already studied. It assumes that a superset of the final graph is initially...

On-line Packing Squares into n Unit Squares

Janusz Januszewski (2010)

Bulletin of the Polish Academy of Sciences. Mathematics

If n ≥ 3, then any sequence of squares of side lengths not greater than 1 whose total area does not exceed ¼(n+1) can be on-line packed into n unit squares.

On-line Ramsey theory.

Grytczuk, J.A., Hałuszczak, M., Kierstead, H.A. (2004)

The Electronic Journal of Combinatorics [electronic only]

On-line ranking number for cycles and paths

Erik Bruoth, Mirko Horňák (1999)

Discussiones Mathematicae Graph Theory

A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number χ * r ( G ) of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that χ * r ( P ₙ ) < 3 l o g ₂ n for n ≥ 2. Here we show...

Onq-Power Cycles in Cubic Graphs

Julien Bensmail (2017)

Discussiones Mathematicae Graph Theory

In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic graphs with no q-power cycles. Concerning the remaining case q = 2 (which corresponds to the conjecture of Erdős and Gyárfás), we show that there exist arbitrarily large cubic graphs whose all 2-power cycles have length 4 only, or 8 only.

Optimal Backbone Coloring of Split Graphs with Matching Backbones

Krzysztof Turowski (2015)

Discussiones Mathematicae Graph Theory

For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c : V (G) → N+ such that |c(u) − c(v)| ≥ 2 for each edge {u, v} ∈ E(H) and |c(u) − c(v)| ≥ 1 for each edge {u, v} ∈ E(G). The backbone chromatic number BBC(G,H) is the smallest integer k such that there exists a backbone coloring with maxv∈V (G) c(v) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.

Optimal bounds for the colored Tverberg problem

Pavle V. M. Blagojević, Benjamin Matschke, Günter M. Ziegler (2015)

Journal of the European Mathematical Society

We prove a “Tverberg type” multiple intersection theorem. It strengthens the prime case of the original Tverberg theorem from 1966, as well as the topological Tverberg theorem of Bárány et al. (1980), by adding color constraints. It also provides an improved bound for the (topological) colored Tverberg problem of Bárány & Larman (1992) that is tight in the prime case and asymptotically optimal in the general case. The proof is based on relative equivariant obstruction theory.

Currently displaying 1261 – 1280 of 1341