Abstract
A graph is said to have {\em bandwidth} at most if there exists a labeling of as such that for every edge . We say that is a {\em balanced -graph} if it is a bipartite graph with bandwidth at most and maximum degree at most , and it also has a proper 2-coloring such that . In this paper, we prove that for every and every natural number , there exists a constant such that for every balanced -graph on vertices we have for all sufficiently large odd . The upper bound is sharp for several classes of graphs. Let be the graph consisting of internally disjoint paths of length all sharing the same endpoints. As a corollary, for each fixed , where if is odd and if is even. In particular, we have , which is a special case of a result of Figaj and Łuczak (2018).
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.