12 papers
Multiple vertex coverings by specified induced subgraphs
Zoltan Furedi, Dhruv Mubayi, Douglas B. West
Given graphs H_1,...,H_k, we study the minimum order of a graph G such that for each i, the induced copies of H_i in G cover V(G). We prove a general upper bound of twice the sum o…
Coloring of Trees with Minimum Sum of Colors
Tao Jiang, Douglas B. West
The chromatic sum of a graph is the smallest sum of colors among all proper colorings with natural numbers. The strength is the minimum number of colors needed to achieve the chrom…
Edge-bandwidth of graphs
Tao Jiang, Dhruv Mubayi, Aditya Shastri +1
The edge-bandwidth of a graph is the minimum, over all labelings of the edges with distinct integers, of the maximum difference between labels of two incident edges. We prove that…
A short proof that ``proper = unit''
Kenneth P. Bogart, Douglas B. West
A short proof is given that the graphs with proper interval representations are the same as the graphs with unit interval representations.
Intersection representation of digraphs in trees with few leaves
In-Jen Lin, Malay K. Sen, Douglas B. West
The leafage of a digraph is the minimum number of leaves in a host tree in which it has a subtree intersection representation. We discuss bounds on the leafage in terms of other pa…
A note on generalized chromatic number and generalized girth
Béla Bollobás, Douglas B. West
Erdős proved that there are graphs with arbitrarily large girth and chromatic number. We study the extension of this for generalized chromatic numbers.