BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an entropy inequality of Shearer.
We refine two results of Jiang, Shao and Vesel on the L(2,1)-labeling number λ of the Cartesian and the strong product of two oriented cycles. For the Cartesian product, we compute the exact value of λ(Cm□Cn) for m, n≥40; in the case of strong product, we either compute the exact value or establish a gap of size one for λ(Cm⊠Cn) for m, n≥48.
Let χk′(G) denote the minimum number of colors needed to color the edges of a graph G in a way that the subgraph spanned by the edges of each color has all degrees congruent to 1(modk). Scott [{\em Discrete Math. 175}, 1-3 (1997), 289--291] proved that χk′(G)≤5k2logk, and thus settled a question of Pyber [{\em Sets, graphs and numbers} (1992), pp. 583--610], who had asked whether χk′(G) can be bounded solely as a function of k. We prove that χk′(G)=O(k), answering affirmatively a question of Scott.
We extend a result of Griggs and Yeh about the maximum possible value of the L(2,1)-labeling number of a graph in terms of its maximum degree to oriented graphs. We consider the problem both in the usual definition of the oriented L(2,1)-labeling number and in some variants we introduce.
We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the edge-disjoint paths problem. We improve the lower bound on the maximum value of Δ(D) which still guarantees that the demand graph D has a realization in Kn,n. We also solve the extremal problem on the number of edges, i.e., we determine the maximum number of edges which guarantees that a demand graph is realizable in Kn,n.
We investigate the terminal-pairibility problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of Δ(D) which still guarantees that the demand graph D is terminal-pairable in this setting. We also prove a sharp theorem on the maximum number of edges such a demand graph can have.
A hypergraph is 2-intersecting if any two edges intersect in at least two vertices. Blais, Weinstein and Yoshida asked (as a first step to a more general problem) whether every 2-intersecting hypergraph has a vertex coloring with a constant number of colors so that each hyperedge e has at least min{|e|,3} colors. We show that there is such a coloring with at most 5 colors (which is best possible).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.