An official website of the United States government
The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $$n$$, the $$n$$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $$\lceil(2n-1)/3\rceil$$ vertices and $$\lfloor(n-2)/3\rfloor$$ isolated vertices. For planar graphs, we show that the extremal $$n$$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $$\lceil(2n-2)/3\rceil$$ vertices and $$\lfloor(n-4)/3\rfloor$$ isolated vertices.
more »
« less
Wheels in planar graphs and Hajós graphs
Abstract It was conjectured by Hajós that graphs containing no ‐subdivision are 4‐colorable. Previous results show that any possible minimum counterexample to Hajós' conjecture, called Hajós graph, is 4‐connected but not 5‐connected. In this paper, we show that if a Hajós graph admits a 4‐cut or 5‐cut with a planar side then the planar side must be small or contains a special wheel. This is a step in our effort to reduce Hajós' conjecture to the Four Color Theorem.
more »
« less
- Award ID(s):
- 1954134
- PAR ID:
- 10248348
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Journal of Graph Theory
- Volume:
- 98
- Issue:
- 2
- ISSN:
- 0364-9024
- Page Range / eLocation ID:
- p. 179-194
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In this note we examine the following random graph model: for an arbitrary graph , with quadratic many edges, construct a graph by randomly adding edges to and randomly coloring the edges of with colors. We show that for a large enough constant and , every pair of vertices in are joined by a rainbow path, that is, israinbow connected, with high probability. This confirms a conjecture of Anastos and Frieze, who proved the statement for and resolved the case when and is a function of .more » « less
-
We study the Bowditch boundaries of relatively hyperbolic group pairs, focusing on the case where there are no cut points. We show that if (G,P) is a rigid relatively hyperbolic group pair whose boundary embeds in S2, then the action on the boundary extends to a convergence group action on S2. More generally, if the boundary is connected and planar with no cut points, we show that every element of P is virtually a surface group. This conclusion is consistent with the conjecture that such a group G is virtually Kleinian. We give numerous examples to show the necessity of our assumptionsmore » « less
-
Abstract A graph $$H$$ is common if the number of monochromatic copies of $$H$$ in a 2-edge-colouring of the complete graph $$K_n$$ is asymptotically minimised by the random colouring. Burr and Rosta, extending a famous conjecture of Erdős, conjectured that every graph is common. The conjectures of Erdős and of Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples of common graphs had not seen much progress since then, although very recently a few more graphs were verified to be common by the flag algebra method or the recent progress on Sidorenko’s conjecture. Our contribution here is to provide several new classes of tripartite common graphs. The first example is the class of so-called triangle trees, which generalises two theorems by Sidorenko and answers a question of Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree $$T$$ , there exists a triangle tree such that the graph obtained by adding $$T$$ as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most $$5$$ vertices yields a common graph.more » « less
-
Abstract Let be a multigraph with maximum degree and chromatic index . If is bipartite then . Otherwise, by a theorem of Goldberg, , where denotes the odd girth of . Stiebitz, Scheide, Toft, and Favrholdt in their book conjectured that if then contains as a subgraph a ring graph with the same chromatic index. Vizing's characterization of graphs with chromatic index attaining the Shannon's bound showed the above conjecture holds for . Stiebitz et al verified the conjecture for graphs with and . McDonald proved the conjecture when is divisible by . In this paper, we show that the chromatic index condition alone is not sufficient to give the conclusion in the conjecture. On the positive side, we show that the conjecture holds for every with , and the maximum degree condition is best possible. This positive result leans on the positive resolution of the Goldberg‐Seymour conjecture.more » « less
