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]

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]

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]

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]

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]

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]

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 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: 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: 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 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]