Given a graph G $G$, we let s+(G) ${s}^{+}(G)$ denote the sum of the squares of the positive eigenvalues of the adjacency matrix of G $G$, and we similarly define s−(G) ${s}^{-}(G)$. We prove that
...χf(G)≥1+maxs+(G)s−(G),s−(G)s+(G) ${\chi }_{f}(G)\ge 1+\max \left\{\frac{{s}^{+}(G)}{{s}^{-}(G)},\frac{{s}^{-}(G)}{{s}^{+}(G)}\right\}$ and thus strengthen a result of Ando and Lin, who showed the same lower bound for the chromatic number χ
(
G
) $\chi (G)$. We in fact show a stronger result wherein we give a bound using the eigenvalues of G $G$ and H $H$ whenever G $G$ has a homomorphism to an edge‐transitive graph H $H$. Our proof utilizes ideas motivated by association schemes.
It is shown that the performance of the maximal scheduling algorithm in wireless ad hoc networks under the hypergraph interference model can be further away from optimal than previously known. The ...exact worst-case performance of this distributed, greedy scheduling algorithm is analyzed.
For a given set M of positive integers, a well-known problem of Motzkin asked to determine the maximal asymptotic density of M-sets, denoted by μ(M), where an M-set is a set of non-negative integers ...in which no two elements differ by an element in M. In 1973, Cantor and Gordon found μ(M) for |M| ≤ 2. Partial results are known in the case |M| ≥ 3 including results in the case when M is an infinite set. This number theory problem is also related to various types of coloring problems of the distance graphs generated by M. In particular, it is known that the reciprocal of the fractional chromatic number of the distance graph generated by M is equal to the value μ(M) when M is finite. Motivated by the families M = {a, b, a + b} and M = {a, b, a + b, b − a} discussed by Liu and Zhu, we study two families of sets M, namely, M = {a, b, b − a, n(a + b)} and M = {a, b, a + b, n(b − a)}. For both of these families, we find some exact values and some bounds on μ(M). We also find bounds on the fractional and circular chromatic numbers of the distance graphs generated by these families. Furthermore, we determine the exact values of chromatic number of the distance graphs generated by these two families.
Let $\chi(G$) and $\chi_f(G)$ denote the chromatic and fractional chromatic numbers of a graph $G$, and let $(n^+ , n^0 , n^-)$ denote the inertia of $G$. We prove that:\1 + \max\left(\frac{n^+}{n^-} ..., \frac{n^-}{n^+}\right) \le \chi(G)\ and conjecture that \ 1 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \le \chi_f(G).\ We investigate extremal graphs for these bounds and demonstrate that this inertial bound is not a lower bound for the vector chromatic number. We conclude with a discussion of asymmetry between $n^+$ and $n^-$, including some Nordhaus-Gaddum bounds for inertia.
It is well known that a random subgraph of the complete graph Kn has chromatic number Θ(n∕logn) w.h.p. Boris Bukh asked whether the same holds for a random subgraph of any n‐chromatic graph, at least ...in expectation. In this paper it is shown that for every graph, whose fractional chromatic number is at least n, the fractional chromatic number of its random subgraph is at least n∕(8log2(4n)) with probability more than 1−12n. This gives the affirmative answer for a strengthening of Bukh's question for the fractional chromatic number.
It is well known that for any k and g, there is a graph with chromatic number at least k and girth at least g. In 1970's, Erdős and Hajnal conjectured that for any numbers k and g, there exists a ...number f(k,g), such that every graph with chromatic number at least f(k, g) contains a subgraph with chromatic number at least k and girth at least g. In 1978, Rödl proved the case for g=4 and arbitrary k. We prove the fractional chromatic number version of Rödl's result.
Given a squarefree monomial ideal
I
⊆
R
=
k
x
1
,
…
,
x
n
, we show that
α
^
(
I
)
, the Waldschmidt constant of
I
, can be expressed as the optimal solution to a linear program constructed from ...the primary decomposition of
I
. By applying results from fractional graph theory, we can then express
α
^
(
I
)
in terms of the fractional chromatic number of a hypergraph also constructed from the primary decomposition of
I
. Moreover, expressing
α
^
(
I
)
as the solution to a linear program enables us to prove a Chudnovsky-like lower bound on
α
^
(
I
)
, thus verifying a conjecture of Cooper–Embree–Hà–Hoefel for monomial ideals in the squarefree case. As an application, we compute the Waldschmidt constant and the resurgence for some families of squarefree monomial ideals. For example, we determine both constants for unions of general linear subspaces of
P
n
with few components compared to
n
, and we compute the Waldschmidt constant for the Stanley–Reisner ideal of a uniform matroid.
We propose a new integer programming formulation for the Fractional Chromatic Number Problem. The formulation is based on representatives of stable sets. In addition, we present a Lagrangian ...heuristic from a Lagrangian relaxation of this formulation to obtain a good feasible solution for the problem. Computational experiments are presented to evaluate and compare the upper and lower bounds provided by our approach.
The tensor product (G1,G2,G3) of graphs G1, G2 and G3 is defined by V(G1,G2,G3)=V(G1)×V(G2)×V(G3)and E(G1,G2,G3)=((u1,u2,u3),(v1,v2,v3)):|{i:(ui,vi)∈E(Gi)}|≥2.Let χf(G) be the fractional chromatic ...number of a graph G. In this paper, we prove that if one of the three graphs G1, G2 and G3 is a circular clique, χf(G1,G2,G3)=min{χf(G1)χf(G2),χf(G1)χf(G3),χf(G2)χf(G3)}.
A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio of a distance graph G is the ...maximum density of an independent set in G. Lih et al. (1999) showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs.
We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three and determine asymptotic values for others.
PDF
