查看更多>>摘要：We present a deterministic distributed algorithm in the LOCAL model that finds a proper (Delta + 1)-edge-coloring of an n-vertex graph of maximum degree Delta in poly(Delta, log n) rounds. This is the first nontrivial distributed edge-coloring algorithm that uses only Delta + 1 colors (matching the bound given by Vizing's theorem). Our approach is inspired by the recent proof of the measurable version of Vizing's theorem due to Grebik and Pikhurko. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：A hereditary class of graphs G is chi-boundedif there exists a function f such that every graph G is an element of G satisfies chi(G) <= f(omega(G)), where chi(G) and omega(G) are the chromatic number and the clique number of G, respectively. As one of the first results about chi-bounded classes, Gyarfas proved in 1985 that if G is P-t-free, i.e., does not contain a t-vertex path as an induced subgraph, then chi (G) <= (t - 1)(omega(G)-1). In 2017, Chudnovsky, Scott, and Seymour proved that C->= t-free graphs, i.e., graphs that exclude induced cycles with at least tvertices, are chi-bounded as well, and the obtained bound is again superpolynomial in the clique number. Note that Pt-1-free graphs are in particular C->= t-free. It remains a major open problem in the area whether for C->= t-free, or at least P-t-free graphs G, the value of chi(G) can be bounded from above by a polynomial function of omega(G). We consider a relaxation of this problem, where we compare the chromatic number with the size of a largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every tthere exists a constant c such that for every l and every C->= t-free graph which does not contain K-l,K-l as a subgraph, it holds that chi(G)<= l(c). (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：Given a graph Hand an integer p, the edge blow-up Hp+1 of His the graph obtained from replacing each edge in H by a clique of order p + 1 where the new vertices of the cliques are all distinct. The Turan numbers for edge blow-up of matchings were first studied by Erdos and Moon. In this paper, we determine the range of the Turan numbers for edge blow-up of all bipartite graphs and the exact Turan numbers for edge blow-up of all non-bipartite graphs. In addition, we characterize the extremal graphs for edge blow-up of all non-bipartite graphs. Our results also extend several known results, including the Turan numbers for edge blow-up of stars, paths and cycles. The method we used can also be applied to find a family of counter-examples to a conjecture posed by Keevash and Sudakov in 2004 concerning the maximum number of edges not contained in any monochromatic copy of H in a 2-edge-coloring of K-n. (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：For positive integers n > d >= k, let phi( n, d, k) denote the least integer phi such that every n-vertex graph with at least phi vertices of degree at least d contains a path on k + 1 vertices. Many years ago, Erdos, Faudree, Schelp and Simonovits proposed the study of the function phi(n, d, k), and conjectured that for any positive integers n > d >= k, it holds that phi(n, d, k) <= right perpendiculark-1/2left perpendicular right perpendicularn/d+1left perpendicular + epsilon, where epsilon = 1 if k is odd and epsilon = 2 otherwise. In this paper we determine the values of the function phi( n, d, k) exactly. This confirms the above conjecture of Erdos et al. for all positive integers k not equal 4 and in a corrected form for the case k = 4. Our proof utilizes, among others, a lemma of Erdos et al. [3], a theorem of Jackson [6], and a (slight) extension of a very recent theorem of Kostochka, Luo and Zirlin [7], where the latter two results concern maximum cycles in bipartite graphs. Moreover, we construct examples to provide answers to two closely related questions raised by Erdos et al. (C) 2021 Elsevier Inc. All rights reserved.
Hosseini, Seyyed AliasgharMohar, BojanAhmadi, Mohammad Bagher
38页
查看更多>>摘要：The atom-bond connectivity (ABC) index is a degree-based molecular descriptor that found diverse chemical applications. Characterizing trees with minimum ABC-index remained an elusive open problem even after serious attempts and is considered by some as one of the most intriguing open problems in mathematical chemistry. In this paper, we describe the exact structure of the extremal trees with sufficiently many vertices and we show how their structure evolves when the number of vertices grows. An interesting fact is that their radius is at most 5 and that all vertices except for one have degree at most 54. In fact, all but at most O(1) vertices have degree 1, 2, 4, or 53. Let gamma(n) = min{ABC(T) : T is a tree of order n}. It is shown that gamma(n) = 1/365 root 1/53 (1 + 26 root 55+ 156 root 106)n + O(1) approximate to 0.67737178 n + O(1). (C) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：We give a simple combinatorial description of an (n - 2k + 2)-chromatic edge-critical subgraph of the Schrijver graph SG(n, k), itself an induced vertex-critical subgraph of the Kneser graph KG(n, k). This extends the main result of Kaiser and Stehlik (2020) [5] to all values of k, and sharpens the classical results of Lovasz and Schrijver from the 1970s. (c) 2021 Elsevier Inc. All rights reserved.
查看更多>>摘要：We give a linear-time algorithm to decide 3-colorability of a triangle-free graph embedded in a fixed surface, and a quadratic-time algorithm to output a 3-coloring in the affirmative case. The algorithms also allow to prescribe the coloring of a bounded number of vertices. (c) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier