More Like this

1. 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
2. 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
3. Spanning bipartite graphs with high degree sum in graphs

   https://doi.org/10.1016/j.disc.2019.111663  

   Chen, Guantao; Chiba, Shuya; Gould, Ronald J.; Gu, Xiaofeng; Saito, Akira; Tsugaki, Masao; Yamashita, Tomoki (February 2020, Discrete Mathematics)
4. Which graphs can be counted in $$C_4$$-free graphs?

   https://doi.org/10.4310/pamq.2022.v18.n6.a4  

   Conlon, David; Fox, Jacob; Sudakov, Benny; Zhao, Yufei (January 2022, Pure and Applied Mathematics Quarterly)
5. Large Monochromatic Components in Almost Complete Graphs and Bipartite Graphs

   https://doi.org/10.37236/9824  

   Füredi, Zoltán; Luo, Ruth (April 2021, The Electronic Journal of Combinatorics)

   Gyárfas proved that every coloring of the edges of $$K_n$$ with $t+1$ colors contains a monochromatic connected component of size at least $n/t$. Later, Gyárfás and Sárközy asked for which values of $$\gamma=\gamma(t)$$ does the following strengthening for almost complete graphs hold: if $$G$$ is an $$n$$-vertex graph with minimum degree at least $$(1-\gamma)n$$, then every $(t+1)$-edge coloring of $$G$$ contains a monochromatic component of size at least $n/t$. We show $$\gamma= 1/(6t^3)$$ suffices, improving a result of DeBiasio, Krueger, and Sárközy. 

   more » « less