Search

Hajnal and Erdős proved that a graph with uncountable chromatic number cannot avoid short cycles, it must contain, for example, C4 (among other obligatory subgraphs). It was shown recently by Soukup that, in contrast of the undirected case, it is consistent that for any n<ω there exists an uncountably dichromatic digraph without directed cycles shorter than n. He asked if it is provable already in ZFC (i.e., Zermelo ‐Fraenkel set theory with the Axiom of choice). We answer his question positively by constructing for every infinite cardinal κ and n<ω a digraph of size 2κ with dichromatic number at least κ+ without directed cycles of length less than n. [ABSTRACT FROM AUTHOR]

As usual, Pn (n≥1) denotes the path on n vertices, and Cn (n≥3) denotes the cycle on n vertices. For a family H of graphs, we say that a graph G is H‐free if no induced subgraph of G is isomorphic to any graph in H. We present a decomposition theorem for the class of (P7,C4,C5)‐free graphs; in fact, we give a complete structural characterization of (P7,C4,C5)‐free graphs that do not admit a clique‐cutset. We use this decomposition theorem to show that the class of (P7,C4,C5)‐free graphs is χ‐bounded by a linear function (more precisely, every (P7,C4,C5)‐free graph G satisfies χ(G)≤3/2ω(G)). We also use the decomposition theorem to construct an O(n3) algorithm for the minimum coloring problem, an O(n2m) algorithm for the maximum weight stable set problem, and an O(n3) algorithm for the maximum weight clique problem for this class, where n denotes the number of vertices and m the number of edges of the input graph. [ABSTRACT FROM AUTHOR]

A subgraph of an edge‐colored graph is said to be properly colored, or shortly PC, if any two adjacent edges have different colors. Fujita, Li, and Zhang gave a decomposition theorem for edge‐colorings of complete bipartite graphs without PC C4. However, their decomposition just focuses on a local structure. In this paper, we give a new and global decomposition theorem for edge‐colorings of complete bipartite graphs without PC C4. Our decomposition gives a corollary on the existence of a monochromatic star with almost sharp bound. [ABSTRACT FROM AUTHOR]

The k‐color bipartite Ramsey number of a bipartite graph H is the least integer n for which every k‐edge‐colored complete bipartite graph Kn,n contains a monochromatic copy of H. The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2‐color Ramsey number of paths. In this paper we determine asymptotically the 3‐color bipartite Ramsey number of paths and (even) cycles. [ABSTRACT FROM AUTHOR]

We show that any complete k‐partite graph G on n vertices, with k≥3, whose edges are two‐coloured, can be covered with two vertex‐disjoint monochromatic paths of distinct colours, given that the largest partition class of G contains at most n∕2 vertices. This extends known results for complete and complete bipartite graphs. Secondly, we show that in the same situation, all but o(n) vertices of the graph can be covered with two vertex‐disjoint monochromatic cycles of distinct colours, if colourings close to a split colouring are excluded. From this we derive that the whole graph, if large enough, may be covered with 14 vertex‐disjoint monochromatic cycles. [ABSTRACT FROM AUTHOR]

Erdős and Moser raised the question of determining the maximum number of maximal cliques or, equivalently, the maximum number of maximal independent sets in a graph on n vertices. Since then there has been a lot of research along these lines. A k‐dominating independent set is an independent set D such that every vertex not contained in D has at least k neighbors in D. Let mik(n) denote the maximum number of k‐dominating independent sets in a graph on n vertices, and let ζk≔limn→∞mik(n)n. Nagy initiated the study of mik(n). In this study, we disprove a conjecture of Nagy using a graph product construction and prove that for any even k we have 1.489≈369≤ζkk. We also prove that for any k≥3 we have ζkk≤2.053(1/(1.053+1∕k))<1.98, improving the upper bound of Nagy. [ABSTRACT FROM AUTHOR]

The famous Kőnig‐Egerváry theorem is equivalent to the statement that the matching number equals the vertex cover number for every induced subgraph of some graph if and only if that graph is bipartite. Inspired by this result, we consider the set Gk of all graphs such that, for every induced subgraph, the maximum number of disjoint paths of order k equals the minimum order of a set of vertices intersecting all paths of order k. For k∈{3,4}, we give complete structural descriptions of the graphs in Gk. Furthermore, for odd k, we give a complete structural description of the graphs in Gk that contain no cycle of order less than k. For these graph classes, our results yield efficient recognition algorithms as well as efficient algorithms that determine maximum sets of disjoint paths of order k and minimum sets of vertices intersecting all paths of order k. [ABSTRACT FROM AUTHOR]

The lexicographic sum of graphs is defined as follows. Let G be a graph. With each v∈V(G) associate a graph Hv. The lexicographic sum of the graphs Hv over G is obtained from G by substituting each v∈V(G) by Hv. Given distinct v,w∈V(G), we have all the possible edges in the lexicographic sum between V(Hv) and V(Hw) if vw∈E(G), and none otherwise. When all the graphs Hv are isomorphic to some graph H, the lexicographic sum of the graphs Hv over G is called the lexicographic product of H by G and is denoted by G≀H. We say that a graph G is fractal if there exists a graph Γ, with at least two vertices, such that G≃Γ≀G. There is a simple way to construct fractal graphs. Let Γ be a graph with at least two vertices. The graph Γω is defined on the set V(Γ)ω of functions from ω to V(Γ) as follows. Given distinct f,g∈V(Γ)ω,fg is an edge of Γω if f(m)g(m) is an edge of Γ, where m is the smallest integer such that f(m)≠g(m). The graph Γω is fractal because Γ≀Γω≃Γ1+ω≃Γω. We prove that a fractal graph is isomorphic to a lexicographic sum over an induced subgraph of Γω, which is itself fractal. [ABSTRACT FROM AUTHOR]

The evasiveness conjecture has been proved for properties of graphs on a prime‐power number of vertices and the six‐vertex case. The 10‐vertex case is still unsolved. In this paper we study the size of the automorphism group of a graph on 2p vertices to estimate the Euler characteristic of monotone nonevasive graph properties. We get some conditions on graphs that such graph properties must contain. We also do this by means of Oliver groups and give a new lower bound for the dimension of the simplicial complex associated with a nontrivial monotone nonevasive graph property. We apply our results to graphs on 10 vertices to get conditions on potential counterexamples to the evasiveness conjecture in the 10‐vertex case. [ABSTRACT FROM AUTHOR]

A graph G is (d1,...,dk)‐colorable if its vertex set can be partitioned into k sets V1,...,Vk, such that for each i∈{1,...,k}, the subgraph of G induced by Vi has maximum degree at most di. The Four Color Theorem states that every planar graph is (0,0,0,0)‐colorable, and a classical result of Cowen, Cowen, and Woodall shows that every planar graph is (2,2,2)‐colorable. In this paper, we extend both of these results to graphs on surfaces. Namely, we show that every graph embeddable on a surface of Euler genus g>0 is (0,0,0,9g−4)‐colorable and (2,2,9g−4)‐colorable. Moreover, these graphs are also (0,0,O(g),O(g))‐colorable and (2,O(g),O(g))‐colorable. We also prove that every triangle‐free graph that is embeddable on a surface of Euler genus g is (0,0,O(g))‐colorable. This is an extension of Grötzsch's Theorem, which states that triangle‐free planar graphs are (0,0,0)‐colorable. Finally, we prove that every graph of girth at least 7 that is embeddable on a surface of Euler genus g is (0,O(g))‐colorable. All these results are best possible in several ways as the girth condition is sharp, the constant maximum degrees cannot be improved, and the bounds on the maximum degrees depending on g are tight up to a constant multiplicative factor. [ABSTRACT FROM AUTHOR]

We show that for every η>0 there exists an integer n0 such that every 2‐coloring of the 3‐uniform complete hypergraph on n≥n0 vertices contains two disjoint monochromatic tight cycles of distinct colors that together cover all but at most ηn vertices. The same result holds if tight cycles are replaced by loose cycles. [ABSTRACT FROM AUTHOR]

An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of C. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out‐degree 2 and two vertices have in‐degree 2). [ABSTRACT FROM AUTHOR]

Mixed graphs can be seen as digraphs that have both arcs and edges (or digons, that is, two opposite arcs). In this article, we consider the case where such graphs are bipartite. As main results, we show that in this context the Moore‐like bound is attained in the case of diameter k=3, and that bipartite‐mixed graphs of diameter k≥4 do not exist. [ABSTRACT FROM AUTHOR]

In this article, we address the maximum number of vertices of induced forests in subcubic graphs with girth at least four or five. We provide a unified approach to prove that every 2‐connected subcubic graph on n vertices and m edges with girth at least four or five, respectively, has an induced forest on at least n−29m or n−15m vertices, respectively, except for finitely many exceptional graphs. Our results improve a result of Liu and Zhao and are tight in the sense that the bounds are attained by infinitely many 2‐connected graphs. Equivalently, we prove that such graphs admit feedback vertex sets with size at most 29m or 15m, respectively. Those exceptional graphs will be explicitly constructed, and our result can be easily modified to drop the 2‐connectivity requirement. [ABSTRACT FROM AUTHOR]

We study a new graph invariant, the sequence {sk} of the number of k‐edge subtrees of a graph. We compute the mean subtree size for several classes of graphs, concentrating on complete graphs, complete bipartite graphs, and theta graphs, in particular. We prove that the ratio of spanning trees to all subtrees in Kn approaches (1/e)(1/e)=0.692201⋯, and give a related formula for Kn,n. We also connect the number of subtrees of Kn that contain a given subtree to the hyperbinomial transform. For theta graphs, we find formulas for the mean subtree size (approximately 23n) and the mode (approximately 22n) of the unimodal sequence {sk}. The main tool is a subtree generating function. [ABSTRACT FROM AUTHOR]

The following question was raised by Tuza in 1990 and Erdős et al. in 1992: if every edge of an n‐vertex chordal graph G is contained in a clique of size at least four, does G have a clique transversal, i.e. a set of vertices meeting all nontrivial maximal cliques, of size at most n/4? We prove that every such graph G has a clique transversal of size at most 2(n−1)/7 if n≥5, which is the best possible bound. [ABSTRACT FROM AUTHOR]

For a given graph H, we say that a graph G on n vertices is H‐saturated if H is not a subgraph of G, but for any edge e∈E(G¯) the graph G+e contains a subgraph isomorphic to H. The set of all values m for which there exists an H‐saturated graph on n vertices and m edges is called the edge spectrum for H‐saturated graphs. In the present article, we study the edge spectrum for H‐saturated graphs when H is a path or a star. In particular, we show that the edge spectrum for star‐saturated graphs consists of all integers between the saturation number and extremal number, and the edge spectrum of path‐saturated graphs includes all integers from the saturation number to slightly below the extremal number, but in general will include gaps just below the extremal number. We also investigate the second largest Pk‐saturated graphs as well as some structural results about path‐saturated graphs that have edge counts close to the extremal number. [ABSTRACT FROM AUTHOR]

A hole is a chordless cycle with at least four vertices. A hole is odd if it has an odd number of vertices. A banner is a graph that consists of a hole on four vertices and a single vertex with precisely one neighbor on the hole. We prove that a (banner, odd hole)‐free graph is perfect, or does not contain a stable set on three vertices, or contains a homogeneous set. Using this structure result, we design a polynomial‐time algorithm for recognizing (banner, odd hole)‐free graphs. We also design polynomial‐time algorithms to find, for such a graph, a minimum coloring, and largest stable set. A graph G is perfectly divisible if every induced subgraph H of G contains a set X of vertices such that X meets all largest cliques of H, and X induces a perfect graph. The chromatic number of a perfectly divisible graph G is bounded by ω2 where ω denotes the number of vertices in a largest clique of G. We prove that (banner, odd hole)‐free graphs are perfectly divisible. [ABSTRACT FROM AUTHOR]

In this article, we are concerned with sufficient conditions for the existence of a {P2,P2k+1}‐factor. We prove that for k≥3, there exists εk>0 such that if a graph G satisfies ∑0≤j≤k−1c2j+1(G−X)≤εk|X| for all X⊆V(G), then G has a {P2,P2k+1}‐factor, where ci(G−X) is the number of components C of G−X with |V(C)|=i. On the other hand, we construct infinitely many graphs G having no {P2,P2k+1}‐factor such that ∑0≤j≤k−1c2j+1(G−X)≤32k+14172k−78|X| for all X⊆V(G). [ABSTRACT FROM AUTHOR]

A vertex dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. In 1988 H. Broersma [5] stated a result implying that every n‐vertex k‐connected graph G such that σ(k+2)(G)≥n−2k−1 contains a vertex dominating path. We provide a short, self‐contained proof of this result and further show that every n‐vertex k‐connected graph such that σ2(G)≥2nk+2+f(k) contains a vertex dominating path of length at most (20k)|T|, where T is a minimum dominating set of vertices. An immediate corollary of this result is that every such graph contains a vertex dominating path with length bounded above by a logarithmic function of the order of the graph. To derive this result, we prove that every n‐vertex k‐connected graph with σ2(G)≥2nk+2+f(k) contains a path of length at most 20k|T|, through any set of T vertices where |T|≤n/900k4. [ABSTRACT FROM AUTHOR]

Abstract: A digraph D is supereulerian if D has a spanning closed ditrail. Bang‐Jensen and Thomassé conjectured that if the arc‐strong connectivity λ ( D ) of a digraph D is not less than the independence number α ( D ), then D is supereulerian. A digraph is bipartite if its underlying graph is bipartite. Let α ′ ( D ) be the size of a maximum matching of D. We prove that if D is a bipartite digraph satisfying λ ( D ) ≥ ⌊ α ′ ( D ) 2 ⌋ + 1, then D is supereulerian. Consequently, every bipartite digraph D satisfying λ ( D ) ≥ ⌊ α ( D ) 2 ⌋ + 1 is supereulerian. The bound of our main result is best possible. [ABSTRACT FROM AUTHOR]

Abstract: A signed graph, denoted by ( G , σ ), is a graph G associated with a mapping σ : E ( G ) → { − 1 , + 1 }. A cycle of ( G , σ ) is a connected 2‐regular subgraph. A cycle C is positive if it has an even number of negative edges, and negative otherwise. A signed‐circuit of a signed graph ( G , σ ) is a positive cycle or a barbell consisting of two edge‐disjoint negative cycles joined by a path. The definition of a signed‐circuit of signed graph comes from the signed‐graphic matroid. A signed‐circuit cover of ( G , σ ) is a family of signed‐circuits covering all edges of ( G , σ ). A signed‐circuit cover with the smallest total length is called a shortest signed‐circuit cover of ( G , σ ) and its length is denoted by scc ( G , σ ). Bouchet proved that a signed graph has a signed‐circuit cover if and only if it is flow‐admissible (i.e., has a nowhere‐zero integer flow). In this article, we show that a 3‐connected flow‐admissible signed graph does not necessarily have a signed‐circuit double cover. For shortest signed‐circuit cover of 2‐edge‐connected cubic signed graphs ( G , σ ), we show that scc ( G , σ ) < 26 | E ( G ) | / 9 if it is flow‐admissible. [ABSTRACT FROM AUTHOR]

Abstract: A matching M in a graph G is uniquely restricted if there is no matching M ′ in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs. [ABSTRACT FROM AUTHOR]

Abstract: In 2015, Bryant, Horsley, Maenhaut, and Smith, generalizing a well‐known conjecture by Alspach, obtained the necessary and sufficient conditions for the decomposition of the complete multigraph λ K n − I into cycles of arbitrary lengths, where I is empty, when λ ( n − 1 ) is even and I is a perfect matching, when λ ( n − 1 ) is odd. Moreover, Bryant in 2010, verifying a conjecture by Tarsi, proved that the obvious necessary conditions for packing pairwise edge‐disjoint paths of arbitrary lengths in λ K n are also sufficient. In this article, first, we obtain the necessary and sufficient conditions for packing edge‐disjoint cycles of arbitrary lengths in λ K n − I. Then, applying this result, we investigate the analogous problem of the decomposition of the complete uniform multihypergraph μ K n ( k ) into Berge cycles and paths of arbitrary given lengths. In particular, we show that for every integer μ ≥ 1, n ≥ 108 and 3 ≤ k < n, μ K n ( k ) can be decomposed into Berge cycles and paths of arbitrary lengths, provided that the obvious necessary conditions hold, thereby generalizing a result by Kühn and Osthus on the decomposition of K n ( k ) into Hamilton Berge cycles. [ABSTRACT FROM AUTHOR]

Abstract: The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for k = 2, in many cases when k = 3, and in many other cases including where the connection set is ± { 1 , 2 , … , k } or ± { 1 , 2 , … , k − 1 , k + 1 }. [ABSTRACT FROM AUTHOR]

Abstract: Let G = ( V , E ) be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least p ( m − 1 ). Let f ( G ) denote the order of a largest full subgraph of G. If p n 2 is a nonnegative integer, define f ( n , p ) = min { f ( G ) : | V ( G ) | = n , | E ( G ) | = p n 2 } .Erdős, Łuczak, and Spencer proved that for n ≥ 2, ( 2 n ) 1 2 − 2 ≤ f ( n , 1 2 ) ≤ 4 n 2 3 ( log n ) 1 3 .In this article, we prove the following lower bound: for n − 2 3 < p n < 1 − n − 1 7, f ( n , p ) ≥ 1 4 ( 1 − p ) 2 3 n 2 3 − 1 .Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of { 1 2 , 2 3 , 3 4 , ⋯ }. In contrast, we show that for any n‐vertex graph G, either G or G c contains a full subgraph on Ω ( n log n ) vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems. [ABSTRACT FROM AUTHOR]

Abstract: We improve by an exponential factor the lower bound of Körner and Muzi for the cardinality of the largest family of Hamilton paths in a complete graph of n vertices in which the union of any two paths has maximum degree 4. The improvement is through an explicit construction while the previous bound was obtained by a greedy algorithm. We solve a similar problem for permutations up to an exponential factor. [ABSTRACT FROM AUTHOR]

Abstract: A path cover of a graph is a set of disjoint paths so that every vertex in the graph is contained in one of the paths. The path cover number p ( G ) of graph G is the cardinality of a path cover with the minimum number of paths. Reed in 1996 conjectured that a 2‐connected 3‐regular graph has path cover number at most ⌈ n / 10 ⌉. In this article, we confirm this conjecture. [ABSTRACT FROM AUTHOR]

Abstract: For minimally k‐connected graphs on n vertices, Mader proved a tight lower bound for the number | V k | of vertices of degree k in dependence on n and k. Oxley observed 1981 that in many cases a considerably better bound can be given if m : = | E | is used as additional parameter, i.e. in dependence on m, n, and k. It was left open to determine whether Oxley's more general bound is best possible. We show that this is not the case, but give a closely related bound that deviates from a variant of Oxley's long‐standing one only for small values of m. We prove that this new bound is best possible. The bound contains Mader's bound as special case. [ABSTRACT FROM AUTHOR]

Abstract: A well‐known theorem of Gomory and Hu states that if G is a finite graph with nonnegative weights on its edges, then there exists a tree T (now called a Gomory‐Hu tree) on V ( G ) such that for all u ≠ v ∈ V ( G ) there is an e ∈ E ( T ) such that the two components of T − e determine an optimal (minimal valued) cut between u an v in G. In this article, we extend their result to infinite weighted graphs with finite total weight. Furthermore, we show by an example that one cannot omit the condition of the finiteness of the total weight. [ABSTRACT FROM AUTHOR]

Abstract: In 1994, J. Chen, J. Gross, and R. Rieper demonstrated how to use the rank of Mohar's overlap matrix to calculate the crosscap‐number distribution, that is, the distribution of the embeddings of a graph in the nonorientable surfaces. That has ever since been by far the most frequent way that these distributions have been calculated. This article introduces a way to calculate the Euler‐genus polynomial of a graph, which combines the orientable and the nonorientable embeddings, without using the overlap matrix. The crosscap‐number polynomial for the nonorientable embeddings is then easily calculated from the Euler‐genus polynomial and the genus polynomial. [ABSTRACT FROM AUTHOR]

Abstract: We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (K6 and K7, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a K8‐minor or contains K2, 2, 2, 2, 2 as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K7‐minor free graph is 8‐colorable and every K8‐minor free graph is 10‐colorable. [ABSTRACT FROM AUTHOR]

Abstract: An immersion of a graph H in another graph G is a one‐to‐one mapping ϕ : V ( H ) → V ( G ) and a collection of edge‐disjoint paths in G, one for each edge of H, such that the path P u v corresponding to the edge u v has endpoints ϕ ( u ) and ϕ ( v ). The immersion is strong if the paths P u v are internally disjoint from ϕ ( V ( H ) ). We prove that every simple graph of minimum degree at least 11 t + 7 contains a strong immersion of the complete graph K t. This improves on previously known bound of minimum degree at least 200t obtained by DeVos et al. Our result supports a conjecture of Lescure and Meyniel (also independently proposed by Abu‐Khzam and Langston), which is the analogue of famous Hadwiger’s conjecture for immersions and says that every graph without a K t‐immersion is ( t − 1 )‐colorable. [ABSTRACT FROM AUTHOR]

Abstract: For a sequence d of nonnegative integers, let G ( d ) and F ( d ) be the sets of all graphs and forests with degree sequence d, respectively. Let γ min ( d ) = min { γ ( G ) : G ∈ G ( d ) }, α max ( d ) = max { α ( G ) : G ∈ G ( d ) }, γ min F ( d ) = min { γ ( F ) : F ∈ F ( d ) }, and α max F ( d ) = max { α ( F ) : F ∈ F ( d ) } where γ ( G ) is the domination number and α ( G ) is the independence number of a graph G. Adapting results of Havel and Hakimi, Rao showed in 1979 that α max ( d ) can be determined in polynomial time. We establish the existence of realizations G ∈ G ( d ) with γ min ( d ) = γ ( G ), and F γ , F α ∈ F ( d ) with γ min F ( d ) = γ ( F γ ) and α max F ( d ) = α ( F α ) that have strong structural properties. This leads to an efficient algorithm to determine γ min ( d ) for every given degree sequence d with bounded entries as well as closed formulas for γ min F ( d ) and α max F ( d ). [ABSTRACT FROM AUTHOR]

Abstract: A tournament is called locally transitive if the outneighborhood and the inneighborhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments W4 and L4, which are the only tournaments up to isomorphism on four vertices containing a unique 3‐cycle. On the other hand, a sequence of tournaments  ( T n ) n ∈ N with  V ( T n ) = n is called almost balanced if all but  o ( n ) vertices of  T n have outdegree  ( 1 / 2 + o ( 1 ) ) n. In the same spirit of quasi‐random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of W4 and L4 in  T n goes to zero as n goes to infinity. [ABSTRACT FROM AUTHOR]

Abstract: We consider (not necessarily proper) colorings of the vertices of a graph where every color is thoroughly dispersed, that is, appears in every open neighborhood. Equivalently, every color is a total dominating set. We define td ( G ) as the maximum number of colors in such a coloring and FTD ( G ) as the fractional version thereof. In particular, we show that every claw‐free graph with minimum degree at least  two has  FTD ( G ) ≥ 3 / 2 and this is best possible. For planar graphs, we show that every triangular disc has FTD ( G ) ≥ 3 / 2 and this is best possible, and that every planar graph has td ( G ) ≤ 4 and this is best possible, while we conjecture that every planar triangulation has td ( G ) ≥ 2. Further, although there are arbitrarily large examples of connected, cubic graphs with td ( G ) = 1, we show that for a connected cubic graph FTD ( G ) ≥ 2 − o ( 1 ). We also consider the related concepts in hypergraphs. [ABSTRACT FROM AUTHOR]

Abstract: We prove that every 3‐connected 2‐indivisible infinite planar graph has a 1‐way infinite 2‐walk. (A graph is 2‐indivisible if deleting finitely many vertices leaves at most one infinite component, and a 2‐walk is a spanning walk using every vertex at most twice.) This improves a result of Timar, which assumed local finiteness. Our proofs use Tutte subgraphs, and allow us to also provide other results when the graph is bipartite or an infinite analog of a triangulation: then the prism over the graph has a spanning 1‐way infinite path. [ABSTRACT FROM AUTHOR]

Abstract: A graph is 1‐planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1‐planar drawing is called 1‐plane. A graph is maximal 1‐planar (1‐plane), if we cannot add any missing edge so that the resulting graph is still 1‐planar (1‐plane). Brandenburg et al. showed that there are maximal 1‐planar graphs with only 45 17 n + O ( 1 ) ≈ 2.647 n edges and maximal 1‐plane graphs with only 7 3 n + O ( 1 ) ≈ 2.33 n edges. On the other hand, they showed that a maximal 1‐planar graph has at least 28 13 n − O ( 1 ) ≈ 2.15 n − O ( 1 ) edges, and a maximal 1‐plane graph has at least 2.1 n − O ( 1 ) edges. We improve both lower bounds to 20 n 9 ≈ 2.22 n. [ABSTRACT FROM AUTHOR]

Abstract: It is conjectured by Berge and Fulkerson that every bridgeless cubic graph has six perfect matchings such that each edge is contained in exactly two of them. Let G be a cubic graph and F = { C 1 , … , C r } be a 2‐factor of G such that | C j | is odd if and only if j ≤ 2 k for some integer k. The 2‐factor F is C(8)‐linked if, for every i ≤ k, there is a circuit D i of length 8 with edge sequence e 1 i … e 8 i where e 1 i , e 5 i ∈ E ( C 2 i − 1 ) and e 3 i , e 7 i ∈ E ( C 2 i ). And the cubic graph G is C(8)‐linked if it contains a C(8)‐linked 2‐factor. It is proved in this article that everyC(8)‐linked cubic graph is Berge–Fulkerson colorable. It is also noticed that many classical families of snarks (including some high oddness snarks) are C(8)‐linked. Consequently, the Berge–Fulkerson conjecture is verified for these infinite families of snarks. [ABSTRACT FROM AUTHOR]

Abstract: This article focuses on the problem of determining the mean orders of sub‐k‐trees of k‐trees. It is shown that the problem of finding the mean order of all sub‐k‐trees containing a given k‐clique C, can be reduced to the previously studied problem of finding the mean order of subtrees of a tree that contain a given vertex. This problem is extended in two ways. The first of these extensions focuses on the mean order of sub‐k‐trees containing a given sub‐k‐tree. The second extension focuses on the expected number of r‐cliques, 1 ≤ r ≤ k + 1, in a randomly chosen sub‐k‐tree containing a fixed sub‐k‐tree X. Sharp lower bounds for both invariants are derived. The article concludes with a study of global mean orders of sub‐k‐trees of a k‐tree. For a k‐tree, from the class of simple‐clique k‐trees, it is shown that the mean order of its sub‐k‐trees is asymptotically equal to the mean subtree order of its dual. For general k‐trees a recursive generating function for the number of sub‐k‐trees of a given k‐tree T is derived. [ABSTRACT FROM AUTHOR]

Abstract: A graph G is hypohamiltonian if G is non‐hamiltonian and for every vertex v in G, the graph G − v is hamiltonian. McKay asked in [J. Graph Theory 85 (2017) 7–11] whether infinitely many planar cubic hypohamiltonian graphs of girth 5 exist. We settle this question affirmatively. [ABSTRACT FROM AUTHOR]

Abstract: An induced matching M in a graph G is dominating if every edge not in M shares exactly one vertex with an edge in M. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph G contains a dominating induced matching. This problem is generally NP‐complete, but polynomial‐time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw‐free graphs. In the present article, we provide a polynomial‐time algorithm to solve the dominating induced matching problem for graphs containing no long claw, that is, no induced subgraph obtained from the claw by subdividing each of its edges exactly once. [ABSTRACT FROM AUTHOR]

Abstract: In this article, we show that every bridgeless graph G of order n and maximum degree Δ has an orientation of diameter at most n − Δ + 3. We then use this result and the definition N G ( H ) = ⋃ v ∈ V ( H ) N G ( v ) ∖ V ( H ), for every subgraph H of G, to give better bounds in the case that G contains certain clusters of high‐degree vertices, namely: For every edge e, G has an orientation of diameter at most n − | N G ( e ) | + 4, if e is on a triangle and at most n − | N G ( e ) | + 5, otherwise. Furthermore, for every bridgeless subgraph H of G, there is such an orientation of diameter at most n − | N G ( H ) | + 3. Finally, if G is bipartite, then we show the existence of an orientation of diameter at most 2 ( | A | − deg G ( s ) ) + 7, for every partite set A of G and s ∈ V ( G ) ∖ A. This particularly implies that balanced bipartite graphs have an orientation of diameter at most n − 2 Δ + 7. For each bound, we give a polynomial‐time algorithm to construct a corresponding orientation and an infinite family of graphs for which the bound is sharp. [ABSTRACT FROM AUTHOR]

A graph G is called [ABSTRACT FROM AUTHOR]

The k-linkage problem is as follows: given a digraph [ABSTRACT FROM AUTHOR]

A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that the KS graphs, K7 and the 13 graphs obtained from K7 by [ABSTRACT FROM AUTHOR]

Tutte's 5-flow conjecture from 1954 states that every bridgeless graph has a nowhere-zero 5-flow. It suffices to prove the conjecture for cyclically 6-edge-connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. This implies that every minimum counterexample to the 5-flow conjecture has oddness at least 6. [ABSTRACT FROM AUTHOR]

Two Hamilton paths in [ABSTRACT FROM AUTHOR]

We construct for all [ABSTRACT FROM AUTHOR]

We prove that every normal plane map (NPM) has a path on three vertices (3-path) whose degree sequence is bounded from above by one of the following triplets: (3, 3, ∞), (3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), and (6,4,7). This description is tight in the sense that no its parameter can be improved and no term dropped. We also pose a problem of describing all tight descriptions of 3-paths in NPMs and make a modest contribution to it by showing that there exist precisely three one-term descriptions: (5, ∞, 6), (5, 10, ∞), and (10, 5, ∞). [ABSTRACT FROM AUTHOR]