The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
Displaying 1261 –
1280 of
1341
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...
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.
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 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 for n ≥ 2. Here we show...
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.
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.
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