More Like this

1. Addressing Johnson Graphs, Complete Multipartite Graphs, Odd Cycles, and Random Graphs

   https://doi.org/10.1080/10586458.2018.1542643  

   Alon, Noga; Cioabă, Sebastian M.; Gilbert, Brandon D.; Koolen, Jack H.; McKay, Brendan D. (January 2019, Experimental Mathematics)
2. Maximum spread of graphs and bipartite graphs

   https://doi.org/10.1090/cams/14  

   Breen, Jane; Riasanovsky, Alex W.; Tait, Michael; Urschel, John (December 2022, Communications of the American Mathematical Society)

   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
3. Wheels in planar graphs and Hajós graphs

   https://doi.org/10.1002/jgt.22687  

   Xie, Qiqin; Xie, Shijie; Yu, Xingxing; Yuan, Xiaofan (June 2021, Journal of Graph Theory)

   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
4. Quasiplanar graphs, string graphs, and the Erdos-Gallai problem

   https://doi.org/10.1007/978-3-031-22203-0_16  

   Fox, J.; Pach, J.; Suk, A. (January 2023, Graph Drawing and Network Visualization. GD 2022. Lecture Notes in Computer Science)
5. Triangle-degrees in graphs and tetrahedron coverings in 3-graphs

   https://doi.org/10.1017/S0963548320000061  

   Falgas-Ravry, Victor; Markström, Klas; Zhao, Yi (March 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 

   more » « less