Which graphs can be counted in $C_4$-free graphs?
- Award ID(s):
- 2154129
- PAR ID:
- 10431296
- Date Published:
- Journal Name:
- Pure and Applied Mathematics Quarterly
- Volume:
- 18
- Issue:
- 6
- ISSN:
- 1558-8599
- Page Range / eLocation ID:
- 2413 to 2432
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Given any graph G G , the spread of G G is the maximum difference between any two eigenvalues of the adjacency matrix of G G . In this paper, we resolve a pair of 20-year-old conjectures of Gregory, Hershkowitz, and Kirkland regarding the spread of graphs. The first states that for all positive integers n n , the n n -vertex graph G G that maximizes spread is the join of a clique and an independent set, with ⌊ 2 n / 3 ⌋ \lfloor 2n/3 \rfloor and ⌈ n / 3 ⌉ \lceil n/3 \rceil vertices, respectively. Using techniques from the theory of graph limits and numerical analysis, we prove this claim for all n n sufficiently large. As an intermediate step, we prove an analogous result for a family of operators in the Hilbert space over L 2 [ 0 , 1 ] \mathscr {L}^2[0,1] . The second conjecture claims that for any fixed m ≤ n 2 / 4 m \leq n^2/4 , if G G maximizes spread over all n n -vertex graphs with m m edges, then G G is bipartite. We prove an asymptotic version of this conjecture. Furthermore, we construct an infinite family of counterexamples, which shows that our asymptotic solution is tight up to lower-order error terms.more » « less
-
more » « less
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.
-
An elastic graph is a graph with an elasticity associated to each edge. It may be viewed as a network made out of ideal rubber bands. If the rubber bands are stretched on a target space there is an elastic energy . We characterize when a homotopy class of maps from one elastic graph to another is loosening , that is, decreases this elastic energy for all possible targets. This fits into a more general framework of energies for maps between graphs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.4310/pamq.2022.v18.n6.a4
