A cellular network is often modeled as a graph and the channel assignment problem is formulated as a coloring problem of the graph. Cellular graphs are used to model hexagonal cell structure of a cellular network. Assuming a 2-band buffering system where the interference does not extend beyond two cells away from the call originating cell, we study a version of the channel assignment problem in cellular graphs that been studied only minimally. In this version, each node has a fixed set of frequency channels where only a subset of which may be available at a given time for communication (as other channels may be busy). Assuming that only a subset of frequency channels are available for communication at each node, we try to determine the size of the smallest set of free channels in a node that will guarantee that each node of the cellular graph can be assigned a channel (from its own set of free channels) that will be interference free in a two band buffering system. The mathematical abstraction of this problem is known as the Choice Number computation problem and is closely related to the List Coloring problem in Graph Theory. In this paper we establish a lower and an upper bound of the distance-2 Choice Number of cellular graphs. In addition we also conduct extensive experimentation to study the impact of the availability of the number of free channels in a node to the percentage of the total number of nodes in the network that can be assigned an interference free channel in a two band buffering system.

Let G and H be balanced $U,V$-bigraphs on $2n$ vertices with $\Delta(H)\leq2$. Let k be the number of components of H, $\delta_U:=\min\{\deg_G(u):u\in U\}$ and $\delta_V:=\min\{\deg_G(v):v\in V\}$. We prove that if n is sufficiently large and $\delta_U+\delta_V\geq n+k$, then G contains H. This answers a question of Amar in the case that n is large. We also show that G contains H even when $\delta_U+\delta_V\geq n+2$ as long as n is sufficiently large in terms of k and $\delta(G)\geq\frac{n}{200k}+1$.

The two-coloring number of graphs, which was originally introduced in the study of the game chromatic number, also gives an upper bound on the degenerate chromatic number as introduced by Borodin. It is proved that the two-coloring number of any planar graph is at most nine. As a consequence, the degenerate list chromatic number of any planar graph is at most nine. It is also shown that the degenerate diagonal chromatic number is at most 11 and the degenerate diagonal list chromatic number is at most 12 for all planar graphs.

A class $\Gamma$ of graphs is $\chi$-bounded if there exists a function f such that $\chi \left(G\right) \leq f \left(\omega \left(G\right) \right)$ for all graphs $G \in \Gamma$, where $\chi$ denotes chromatic number and $\omega$ denotes clique number. Gyárfás and Sumner independently conjectured that, for any tree T, the class ${\rm Forb} \left(T\right)$, consisting of graphs that do not contain T as an induced subgraph, is $\chi$-bounded. The first author and Penrice showed that this conjecture is true for any radius two tree. Here we use the work of several authors to show that the conjecture is true for radius three trees obtained from radius two trees by making exactly one subdivision in every edge adjacent to the root. These are the only trees with radius greater than two, other than subdivided stars, for which the conjecture is known to be true.

Sauer [Combinatorics, 1 (1993), pp. 361--377] has conjectured that for any tree T and any clique K, the class Forb(T, K) of graphs that induces neither T nor K is not vertex Ramsey. This conjecture is implied by an even stronger conjecture of Gyárfás and independently by Sumner, that Forb(T, K) is $\chi$-bounded. Until now, for all trees T, if Forb(T, K) was known to not be vertex Ramsey, then Forb(T, K) was also known to be $\chi$-bounded. In this paper we introduce a new class of trees, spiders with toes, which includes all trees T such that Forb(T) is known to be $\chi$-bounded as well as other trees for which it is not known to be $\chi$-bounded. We show that for every spider with toes T, Forb(T, K) is not vertex Ramsey.

For a graph H, let ${\text{Forb}}( H )$ be the class of graphs that do not induce H, and let $P_5 $ be the path on five vertices. In this article, we answer two questions of Gyárfás and Lehel. First, we show that there exists a function $f( \omega )$ such that for any graph $G \in \,{\text{Forb}}( P_5 )$, the on-line coloring algorithm First-Fit uses at most $f( \omega ( G ) )$ colors on G, where $\omega ( G )$ is the clique size of G. Second, we show that there exists an on-line algorithm A that will color any graph $G \in \,{\text{Forb}}( P_5 )$ with a number of colors exponential in $\omega ( G )$. Finally, we extend some of our results to larger classes of graphs defined in terms of a list of forbidden subgraphs.

An on-line vertex coloring algorithm receives the vertices of a graph in some externally determined order, and, whenever a new vertex is presented, the algorithm also learns to which of the previously presented vertices the new vertex is adjacent. As each vertex is received, the algorithm must make an irrevocable choice of a color to assign the new vertex, and it makes this choice without knowledge of future vertices. A class of graphs $\Gamma $ is said to be on-line $\chi$-bounded if there exists an on-line algorithm A and a function f such that A uses at most $f( \omega ( G ) )$ colors to properly color any graph G in $\Gamma $. If H is a graph, let Forb$( H )$ denote the class of graphs that do not induce H. The goal of this paper is to establish that Forb$( T )$ is on-line $\chi$-bounded for every radius-2 tree T. As a corollary, the authors answer a question of Schmerl’s the authors show that every recursive cocomparability graph can be recursively colored with a number of colors that depends only on its clique number.

It is shown that First-Fit coloring requires at most $40\omega $ colors to color an interval graph with clique size $\omega $. It follows that a polynomial time approximation algorithm for Dynamic Storage Allocation due to Chrobak and Slusarek has a constant performance ratio of 80.

If σ is the order type of a recursive linear order which has a nontrivial automorphism, we let denote the least complexity in the arithmetical hierarchy such that every recursive order of type σ has a nontrivial automorphism of complexity . In Chapter 16 of his book Linear orderings [R], Rosenstein discussed the problem of determining for certain order types σ. For example Rosenstein proved that , where ζ is the order type of the integers, by constructing a recursive linear order of type ζ which has no nontrivial Σ1-automorphism and showing that every recursive linear order of type ζ has a nontrivial Π1-automorphism. Rosenstein also considered linear orders of order type 2 · η, where 2 is the order type of a two-element chain and η is the order type of the rational numbers. It is easily seen that any recursive linear order of type 2 · η has a nontrivial ⊿2-automorphism; he showed that there is a recursive linear order of type 2 · η that has no nontrivial Σ1-automorphism. This left the question, posed in [R] and also by Lerman and Rosenstein in [LR], of whether or ⊿2. The main result of this article is that :

Ehrenfeucht and Mostowski [3] introduced the notion of indiscernibles and proved that every first order theory has a model with an infinite set of order indiscernibles. Since their work, techniques involving indiscernibles have proved to be extremely useful for constructing models with various specialized properties. In this paper and in a sequel [5], we investigate the effective content of Ehrenfeucht's and Mostowski's result. In this paper we consider the question of which decidable theories have decidable models with infinite recursive sets of indiscernibles. In §1, using some basic facts from stability theory, we show that certain large classes of decidable theories have decidable models with infinite recursive sets of indiscernibles. For example, we show that every ω-stable decidable theory and every stable theory which possesses a certain strong decidability property called ∃Q-decidability have such models. In §2 we construct several examples of decidable theories which have no decidable models with infinite recursive sets of indiscernibles. These examples show that our hypothesis for our positive results in §1 are necessary. Finally in §3 we give two applications of our results. First as an easy application of our results in §1, we show that every ω-stable decidable theory has uncountable models which realize only recursive types. Also our counterexamples in §2 allow us to answer negatively two questions of Baldwin and Kueker [1] concerning the effectiveness of their elimination of Ramsey quantifiers for certain theories. In [5], we show that in general the problem of finding an infinite set of indiscernibles in a decidable model is recursively equivalent to finding a path through a recursive infinite branching tree. Similarly, we show that the problem of finding an co-type of a set of indiscernibles in a decidable ω-categorical theory is recursively equivalent to finding a path through a highly recursive finitely branching tree.