Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G) <= box(G) log(2) alpha(G], where alpha(G) is the maximum size of an independent set in G. In this note we show that cub(G) <= 2 log(2) X (G)] box(G) + X (G) log(2) alpha(G)], where x (G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G) <= 2(box(G) + log(2) alpha(G)] Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every epsilon > 0, the value given by our upper bound is at most (1 + epsilon) times their cubicity. Thus, our upper bound is almost tight. (c) 2015 Elsevier B.V. All rights reserved.

Inhibition of p300 lysine acetyltransferase activity by luteolin reduces tumor growth in head and neck squamous cell carcinoma (HNSCC) xenograft mouse model

Chromatin acetylation is attributed with distinct functional relevance with respect to gene expression in normal and diseased conditions thereby leading to a topical interest in the concept of epigenetic modulators and therapy. We report here the identification and characterization of the acetylation inhibitory potential of an important dietary flavonoid, luteolin. Luteolin was found to inhibit p300 acetyltransferase with competitive binding to the acetyl CoA binding site. Luteolin treatment in a xenografted tumor model of head and neck squamous cell carcinoma (HNSCC), led to a dramatic reduction in tumor growth within 4 weeks corresponding to a decrease in histone acetylation. Cells treated with luteolin exhibit cell cycle arrest and decreased cell migration. Luteolin treatment led to an alteration in gene expression and miRNA profile including up-regulation of p53 induced miR-195/215, let7C; potentially translating into a tumor suppressor function. It also led to down regulation of oncomiRNAs such as miR-135a, thereby reflecting global changes in the microRNA network. Furthermore, a direct correlation between the inhibition of histone acetylation and gene expression was established using chromatin immunoprecipitation on promoters of differentially expressed genes. A network of dysregulated genes and miRNAs was mapped along with the gene ontology categories, and the effects of luteolin were observed to be potentially at multiple levels: at the level of gene expression, miRNA expression and miRNA processing.