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
The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.
Given a 3-colorable graph X, the 3-coloring complex B(X) is the graph whose vertices are all the independent sets which occur as color classes in some 3-coloring of X. Two color classes C,D∈V(B(X)) are joined by an edge if C and D appear together in a 3-coloring of X. The graph B(X) is 3-colorable. Graphs for which B(B(X)) is isomorphic to X are termed reflexive graphs. In this paper, we consider 3-edge-colorings of cubic graphs for which we allow half-edges. Then we consider the 3-coloring complexes of their line graphs. The main result of the paper is a surprising outcome that the line graph of any connected cubic triangle-free outerplanar graph is reflexive. We also exhibit some other interesting classes of reflexive line graphs.
Motivated by the study of the crossing number of graphs, it is shown that, for trees, the sum of the products of the degrees of the end-vertices of all edges has an upper bound in terms of the sum of all vertex degrees to the power of ϕ2, where ϕ is the golden ratio. The exponent ϕ2 is best possible. This inequality is generalized for all graphs with bounded maximum average degree.
An orientation of a graph G is proper if any two adjacent vertices have different indegrees. The proper orientation number χ(G) of a graph G is the minimum of the maximum indegree, taken over all proper orientations of G. In this paper, we show that a connected bipartite graph may be properly oriented even if we are only allowed to control the orientation of a specific set of edges, namely, the edges of a spanning tree and all the edges incident to one of its leaves. As a consequence of this result, we prove that 3-connected planar bipartite graphs have proper orientation number at most 6. Additionally, we give a short proof that χ(G)≤4, when G is a tree and this proof leads to a polynomial-time algorithm to proper orient trees within this bound.
Let H be a k-graph on n vertices, with minimum codegree at least n/k+cn for some fixed c>0. In this paper we construct a polynomial-time algorithm which finds either a perfect matching in H or a certificate that none exists. This essentially solves a problem of Karpiński, Ruciński and Szymańska; Szymańska previously showed that this problem is NP-hard for a minimum codegree of n/k−cn. Our algorithm relies on a theoretical result of independent interest, in which we characterise any such hypergraph with no perfect matching using a family of lattice-based constructions.
We show that if pn >> log n, the binomial random graph G_{n,p} has an approximate Hamilton decomposition. More precisely, we show that in this range G_{n,p} contains a set of edge-disjoint Hamilton cycles covering almost all of its edges. This is best possible in the sense that the condition that pn >> log n is necessary.
We show that provided log50n/n≤p≤1−n−1/4log9n we can with high probability find a collection of ⌊δ(G)/2⌋ edge-disjoint Hamilton cycles in G∼Gn,p, plus an additional edge-disjoint matching of size ⌊n/2⌋ if δ(G) is odd. This confirms, for the above range of p, a conjecture of Frieze and Krivelevich.
Boettcher, Schacht and Taraz gave a condition on the minimum degree of a graph G on n vertices that ensures G contains every r-chromatic graph H on n vertices of bounded degree and of bandwidth o(n), thereby proving a conjecture of Bollobas and Komlos. We strengthen this result in the case when H is bipartite. Indeed, we give an essentially best-possible condition on the degree sequence of a graph G on n vertices that forces G to contain every bipartite graph H on n vertices of bounded degree and of bandwidth o(n). This also implies an Ore-type result. In fact, we prove a much stronger result where the condition on G is relaxed to a certain robust expansion property. Our result also confirms the bipartite case of a conjecture of Balogh, Kostochka and Treglown concerning the degree sequence of a graph which forces a perfect H-packing.
In this paper, we construct two hypergraphs which exhibit the following properties. We first construct a hypergraph GCP and show that Breaker wins the Maker-Breaker game on GCP, but Chooser wins the Chooser-Picker game on GCP. This disproves an (informally stated) conjecture of Beck. Our second construction relates to Beck's Neighbourhood Conjecture, which (in its weakest form) states that there exists c>1 such that Breaker wins the Maker-Breaker game on any n-uniform hypergraph G of maximum degree at most cn. We consider the case n=4 and construct a 4-graph G4 with maximum vertex degree 3, such that Maker wins the Maker-Breaker game on G4. This answers a question of Leader.
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.