Birmele [*J Graph Theory* 2003] proved that every graph with circumference *t* has treewidth at most . Under the additional assumption of 2-connectivity, such graphs have bounded pathwidth, which is a qualitatively stronger conclusion. Birmele's theorem was extended by Birmele et al. [*Combinatorica* 2007] who showed that every graph without *k* disjoint cycles of length at least *t* has treewidth . Our main result states that, under the additional assumption of -connectivity, such graphs have bounded pathwidth. In fact, they have pathwidth . Moreover, examples show that -connectivity is required for bounded pathwidth to hold. These results suggest the following general question: for which values of *k* and graphs *H* does every *k*-connected *H*-minor-free graph have bounded pathwidth? We discuss this question and provide a few observations.

Erdős, Gallai, and Tuza posed the following problem: given an *n*-vertex graph *G*, let denote the smallest size of a set of edges whose deletion makes *G* triangle-free, and let denote the largest size of a set of edges containing at most one edge from each triangle of *G*. Is it always the case that ? We have two main results. We first obtain the upper bound , as a partial result toward the Erdős–Gallai–Tuza conjecture. We also show that always , where *m* is the number of edges in *G*; this bound is sharp in several notable cases.

For positive integers *n* and *s*, a subset [*n*] is *s*-stable if for distinct . The *s*-stable *r*-uniform Kneser hypergraph is the *r*-uniform hypergraph that has the collection of all *s*-stable *k*-element subsets of [*n*] as vertex set and whose edges are formed by the *r*-tuples of disjoint *s*-stable *k*-element subsets of [*n*]. Meunier () conjectured that for positive integers with , and , the chromatic number of *s*-stable *r* -uniform Kneser hypergraphs is equal to . It is a generalized version of the conjecture proposed by Alon et al. (). Alon et al. () confirmed Meunier's conjecture for with arbitrary positive integer *q*. Lin et al. () studied the *k*th chromatic number of the Mycielskian of the ordinary Kneser graphs for . They conjectured that for . The case was proved by Mycielski (). Lin et al. () confirmed their conjecture for , or when *n* is a multiple of *k* or .In this paper, we investigate the multichromatic number of the usual *s* -stable Kneser graphs . With the help of Fan's (1952) combinatorial lemma, we show that Meunier's conjecture is true for *r* is a power of 2 and *s* is a multiple of *r*, and Lin-Liu-Zhu's conjecture is true for .

We prove a conjecture of Ohba that says that every graph *G* on at most vertices satisfies .

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half-open unit intervals of the real line. This is a proper superclass of the well-known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach, and Szwarcfiter (Mixed unit interval graphs, Discrete Math 312, 3357–3363 (2012)).

Let *G* be a connected simple graph, and let *f* be a mapping from to the set of integers. This paper is concerned with the existence of a spanning tree in which each vertex *v* has degree at least . We show that if for any nonempty subset , then a connected graph *G* has a spanning tree such that for all , where is the set of neighbors *v* of vertices in *S* with , , and is the degree of *x* in *T*. This is an improvement of several results, and the condition is best possible.

Consider the random graph process that starts from the complete graph on *n* vertices. In every step, the process selects an edge uniformly at random from the set of edges that are in a copy of a fixed graph *H* and removes it from the graph. The process stops when no more copies of *H* exist. When *H* is a strictly 2-balanced graph we give the exact asymptotics on the number of edges remaining in the graph when the process terminates and investigate some basic properties namely the size of the maximal independent set and the presence of subgraphs.

We prove that every tournament *T* with no three disjoint cycles contains a set *X* of at most four vertices such that is acyclic.

A graph *G* with at least vertices is said to be distance *d m*-extendable if for any matching *M* of *G* with *m* edges in which the edges lie at distance at least *d* pairwise, there exists a perfect matching of *G* containing *M*. In this article we prove that every 5-connected triangulation on the plane of even order is distance 3 9-extendable and distance 4 *m*-extendable for any *m*.

We show that a graph-like continuum embeds in some surface if and only if it does not contain one of: a generalized thumbtack; or infinitely many *K*_{3, 3}s or *K*_{5}s that are either pairwise disjoint or all have just a single point in common.

A signed graph is a graph *G* together with an assignment of signs + and − to all the edges of *G* where Σ is the set of negative edges. Furthermore and are considered to be equivalent if the symmetric difference of Σ_{1} and Σ_{2} is an edge cut of *G*. Naturally arising from matroid theory, several notions of graph theory, such as the theory of minors and the theory of nowhere-zero flows, have been already extended to signed graphs. In an unpublished manuscript, B. Guenin introduced the notion of signed graph homomorphisms where he showed how some well-known conjectures can be captured using this notion. A signed graph is said to map to if there is an equivalent signed graph of and a mapping such that (*i*) if then and if and only if . The chromatic number of a signed graph can then be defined as the smallest order of a homomorphic image of . Capturing the notion of graph homomorphism order, signed graph homomorphisms provide room for extensions and strengthenings of most homomorphism and coloring theories on graphs. Thus this paper is the first general study of signed graph homomorphisms. In this work, our focus would be on the relation of homomorphisms of signed graphs with minors of signed graphs. After a thorough introduction to the concept we show that the notion of signed graph homomorphism on the set of signed graphs whose underlying graph is bipartite already captures the standard notion of graph homomorphism. We prove that the largest planar signed clique is of order 8. For the maximum chromatic number of planar signed graphs we give the lower bound of 10 and the upper bound of 48. We determine this maximum for some other families such as outerplanar signed graphs. Finally, reformulating Hadwiger's conjecture in the language of homomorphism of signed graphs whose underlying graph is bipartite, we show that while some stronger form of the conjecture holds for small chromatic number, such strengthening of the conjecture would not hold for large chromatic numbers. This could be regarded as a first indication that perhaps Hadwiger's conjecture only holds for small chromatic numbers.

In this note, we prove that every triangulation *G* on any closed surface has domination number at most . This unifies some results on the domination number of a triangulation on a closed surface.

For graphs *G* and *H*, a homomorphism from *G* to *H*, or *H*-coloring of *G*, is a map from the vertices of *G* to the vertices of *H* that preserves adjacency. When *H* is composed of an edge with one looped endvertex, an *H*-coloring of *G* corresponds to an independent set in *G*. Galvin showed that, for sufficiently large *n*, the complete bipartite graph is the *n*-vertex graph with minimum degree δ that has the largest number of independent sets. In this article, we begin the project of generalizing this result to arbitrary *H*. Writing for the number of *H*-colorings of *G*, we show that for fixed *H* and or ,

for any *n*-vertex *G* with minimum degree δ (for sufficiently large *n*). We also provide examples of *H* for which the maximum is achieved by and other *H* for which the maximum is achieved by . For (and sufficiently large *n*), we provide an infinite family of *H* for which for any *n*-vertex *G* with minimum degree δ. The results generalize to weighted *H*-colorings.

The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a given rank and characterize all such graphs achieving the maximum order.

If a graph *G* decomposes into edge-disjoint 4-cycles, then each vertex of *G* has even degree and 4 divides the number of edges in *G*. It is shown that these obvious necessary conditions are also sufficient when *G* is any simple graph having minimum degree at least , where *n* is the number of vertices in *G*. This improves the bound given by Gustavsson (PhD Thesis, University of Stockholm, 1991), who showed (as part of a more general result) sufficiency for simple graphs with minimum degree at least . On the other hand, it is known that for arbitrarily large values of *n* there exist simple graphs satisfying the obvious necessary conditions, having *n* vertices and minimum degree , but having no decomposition into edge-disjoint 4-cycles. We also show that if *G* is a bipartite simple graph with *n* vertices in each part, then the obvious necessary conditions for *G* to decompose into 4-cycles are sufficient when *G* has minimum degree at least .

A graph *G* is *almost hypohamiltonian* if *G* is non-hamiltonian, there exists a vertex *w* such that is non-hamiltonian, and for any vertex the graph is hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4-connected almost hypohamiltonian graph, while Thomassen's question whether 4-connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order *n* for every . During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.

Let *D* be a digraph with vertex set and arc set . A vertex *x* is a *k*-king of *D*, if for every , there is an -path of length at most *k*. A subset *N* of is *k*-independent if for every pair of vertices , we have and ; it is *l*-absorbent if for every there exists such that . A -kernel of *D* is a *k*-independent and *l*-absorbent subset of . A *k*-kernel is a -kernel. A digraph *D* is *k*-quasitransitive, if for any path of length *k*, *x*_{0} and are adjacent. In this article, we will prove that a *k*-quasitransitive digraph with has a *k*-king if and only if it has a unique initial strong component and the unique initial strong component is not isomorphic to an extended -cycle where each has at least two vertices. Using this fact, we show that every strong *k*-quasitransitive digraph has a -kernel.

Given graphs *G* and *H* with , suppose that we have a -path in *G* for each edge in *H*. There are obvious additional conditions that ensure that *G* contains *H* as a rooted subgraph, subdivision, or immersion; we seek conditions that ensure that *G* contains *H* as a rooted minor or minor. This naturally leads to studying sets of paths that form an *H*-immersion, with the additional property that paths that contain the same vertex must have a common endpoint. We say that *H* is *contractible* if, whenever *G* contains such an *H*-immersion, *G* must also contain a rooted *H*-minor. We show, for example, that forests, cycles, *K*_{4}, and *K*_{1, 1, 3} are contractible, but that graphs that are not 6-colorable and graphs that contain certain subdivisions of *K*_{2, 3} are not contractible.

A (di)graph is supereulerian if it contains a spanning eulerian sub(di)graph. This property is a relaxation of hamiltonicity. Inspired by this analogy with hamiltonian cycles and by similar results in supereulerian graph theory, we analyze a number of sufficient Ore type conditions for a digraph to be supereulerian. Furthermore, we study the following conjecture due to Thomassé and the first author: if the arc-connectivity of a digraph is not smaller than its independence number, then the digraph is supereulerian. As a support for this conjecture we prove it for digraphs that are semicomplete multipartite or quasitransitive and verify the analogous statement for undirected graphs.

In recent articles by Grohe and Marx, the treewidth of the line graph of a complete graph is a critical example—in a certain sense, every graph with large treewidth “contains” . However, the treewidth of was not determined exactly. We determine the exact treewidth of the line graph of a complete graph.

A triangle-free graph *G* is called *k-existentially complete* if for every induced *k*-vertex subgraph *H* of *G*, every extension of *H* to a -vertex triangle-free graph can be realized by adding another vertex of *G* to *H*. Cherlin asked whether *k*-existentially complete triangle-free graphs exist for every *k*. Here, we present known and new constructions of 3-existentially complete triangle-free graphs.

In the article, the existence of rainbow cycles in edge colored plane triangulations is studied. It is shown that the minimum number of colors that force the existence of a rainbow *C*_{3} in any *n*-vertex plane triangulation is equal to . For a lower bound and for an upper bound of the number is determined.

Let *G* be a graph of order *n*. Let *W* be a subset of with , where *k* is a positive integer. We show that if for each , then *G* contains *k* vertex-disjoint cycles covering *W* such that each of the *k* cycles contains at least three vertices of *W*.

For given integers we ask whether every large graph with a sufficiently *small* number of *k*-cliques and *k*-anticliques must contain an induced copy of every *l*-vertex graph. Here we prove this claim for with a sharp bound. A similar phenomenon is established as well for tournaments with .

It is shown that if *K* is any regular complete multipartite graph of even degree, and *F* is any bipartite 2-factor of *K*, then there exists a factorization of *K* into *F*; except that there is no factorization of *K*_{6, 6} into *F* when *F* is the union of two disjoint 6-cycles.

We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an *H*-factor in a random graph . We prove that the conjectured threshold function is correct for any graph *H* which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model.

A matching *M* of a graph *G* is a dominating induced matching (DIM) of *G* if every edge of *G* is either in *M* or adjacent with exactly one edge in *M*. We prove sharp upper bounds on the number of DIMs of a graph *G* and characterize all extremal graphs. Our results imply that if *G* is a graph of order *n*, then ; provided *G* is triangle-free; and provided and *G* is connected.

Seymour conjectured that every oriented simple graph contains a vertex whose second neighborhood is at least as large as its first. Seymour's conjecture has been verified in several special cases, most notably for tournaments by Fisher . One extension of the conjecture that has been used by several researchers is to consider vertex-weighted digraphs. In this article we introduce a version of the conjecture for arc-weighted digraphs. We prove the conjecture in the special case of arc-weighted tournaments, strengthening Fisher's theorem. Our proof does not rely on Fisher's result, and thus can be seen as an alternate proof of said theorem.

The *clique number* of a digraph *D* is the size of the largest bidirectionally complete subdigraph of *D*. *D* is *perfect* if, for any induced subdigraph *H* of *D*, the dichromatic number defined by Neumann-Lara (The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982), 265–270) equals the clique number . Using the Strong Perfect Graph Theorem (M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), 51–229) we give a characterization of perfect digraphs by a set of forbidden induced subdigraphs. Modifying a recent proof of Bang-Jensen et al. (Finding an induced subdivision of a digraph, Theoret. Comput. Sci. 443 (2012), 10–24) we show that the recognition of perfect digraphs is co--complete. It turns out that perfect digraphs are exactly the complements of clique-acyclic superorientations of perfect graphs. Thus, we obtain as a corollary that complements of perfect digraphs have a kernel, using a result of Boros and Gurvich (Perfect graphs are kernel solvable, Discrete Math. 159 (1996), 35–55). Finally, we prove that it is -complete to decide whether a perfect digraph has a kernel.

The article characterizes -regular graphs with circular flow number . For this is Tutte's characterization of cubic graphs with flow number 4. The class of cubic graphs is the only class of odd regular graphs where a flow number separates the class 1 graphs from the class 2 graphs. We finally state some conjectures and relate them to Jaeger's circular flow conjecture and Tutte's 3-flow conjecture.

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw-free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw-free graphs with a three-colorable complement. To prove our results, we introduce a very useful χ-preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so-called *skeletal* graphs.

The square *G*^{2} of a graph *G* is the graph defined on such that two vertices *u* and *v* are adjacent in *G*^{2} if the distance between *u* and *v* in *G* is at most 2. Let and be the chromatic number and the list chromatic number of a graph *H*, respectively. A graph *H* is called *chromatic-choosable* if . It is an interesting problem to find graphs that are chromatic-choosable. Kostochka and Woodall (Choosability conjectures and multicircuits, Discrete Math., 240 (2001), 123–143) conjectured that for every graph *G*, which is called List Square Coloring Conjecture. In this article, we give infinitely many counter examples to the conjecture. Moreover, we show that the value can be arbitrarily large.

Let *G* be a bridgeless cubic graph. Consider a list of *k* 1-factors of *G*. Let be the set of edges contained in precisely *i* members of the *k* 1-factors. Let be the smallest over all lists of *k* 1-factors of *G*. Any list of three 1-factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge-covers and for the existence of three 1-factors with empty intersection. Furthermore, if , then is an upper bound for the girth of *G*. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with have a 4-cycle cover of length and a 5-cycle double cover. These graphs also satisfy two conjectures of Zhang . We also give a negative answer to a problem stated in .

For a class of graphs *X*, let be the number of graphs with vertex set in the class *X*, also known as the speed of *X*. It is known that in the family of hereditary classes (i.e. those that are closed under taking induced subgraphs) the speeds constitute discrete layers and the first four lower layers are constant, polynomial, exponential, and factorial. For each of these four layers a complete list of minimal classes is available, and this information allows to provide a global structural characterization for the first three of them. The minimal layer for which no such characterization is known is the factorial one. A possible approach to obtaining such a characterization could be through identifying all minimal superfactorial classes. However, no such class is known and possibly no such class exists. To overcome this difficulty, we employ the notion of boundary classes that has been recently introduced to study algorithmic graph problems and reveal the first few boundary classes for the factorial layer.

A *rainbow matching* for (not necessarily distinct) sets of hypergraph edges is a matching consisting of *k* edges, one from each . The aim of the article is twofold—to put order in the multitude of conjectures that relate to this concept (some first presented here), and to prove partial results on one of the central conjectures.

Let *C* be a given circuit of a bridgeless cubic graph *G*. It was conjectured by Seymour that *G* has a circuit double cover (CDC) containing the given circuit *C*. This conjecture (strong CDC [SCDC] conjecture) has been verified by Fleischner and Häggkvist for various families of graphs and circuits. In this article, some of these earlier results have been improved: (1) if contains a Hamilton path or a *Y*-tree of order less than 14, then *G* has a CDC containing *C*; (2) if is connected and , then *G* has a CDC containing *C*.

Asteroidal Triple-free (AT-free) graphs have received considerable attention due to their inclusion of various important graphs families, such as interval and cocomparability graphs. The asteroidal number of a graph is the size of a largest subset of vertices such that the removal of the closed neighborhood of any vertex in the set leaves the remaining vertices of the set in the same connected component. (AT-free graphs have asteroidal number at most 2.) In this article, we characterize graphs of bounded asteroidal number by means of a vertex elimination ordering, thereby solving a long-standing open question in algorithmic graph theory. Similar characterizations are known for chordal, interval, and cocomparability graphs.

Immersion is a containment relation on graphs that is weaker than topological minor. (Every topological minor of a graph is also its immersion.) The graphs that do not contain any of the Kuratowski graphs (*K*_{5} and *K*_{3, 3}) as topological minors are exactly planar graphs. We give a structural characterization of graphs that exclude the Kuratowski graphs as immersions. We prove that they can be constructed from planar graphs that are subcubic or of branch-width at most 10 by repetitively applying *i*-edge-sums, for . We also use this result to give a structural characterization of graphs that exclude *K*_{3, 3} as an immersion.

Bouchet's conjecture asserts that each signed graph which admits a nowhere-zero flow has a nowhere-zero 6-flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow-admissible graph admits a nowhere-zero 4-flow and we characterise those which have a nowhere-zero 2-flow and a nowhere-zero 3-flow.

Given two graphs *F* and *G*, an *induced* *F*-decomposition of *G* is a partition of into induced subgraphs isomorphic to *F*. Bondy and Szwarcfiter [*J. Graph Theory*, DOI: 10.1002/jgt.21654] defined the value as the maximum number of edges in a graph of order *n* admitting an *induced* *F*-decomposition and determined the value of for some graphs (and families of graphs). In this article, we prove that is valid for all graphs *F*. We also present tighter asymptotic bounds for some of the small graphs for which the exact value of remains unknown. The proofs are based on the heavy use of various classes of Kneser graphs and hypergraphs.

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, that is, can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let denote the number of cops needed to capture the robber in a graph *G* in this variant, and let denote the treewidth of *G*. We show that if *G* is planar then , and there is a polynomial-time constant-factor approximation algorithm for computing . We also determine, up to constant factors, the value of of the Erdős–Rényi random graph for all admissible values of *p*, and show that when the average degree is ω(1), is typically asymptotic to the domination number.

Let *U*_{5} be the tournament with vertices *v*_{1}, …, *v*_{5} such that , and if , and . In this article, we describe the tournaments that do not have *U*_{5} as a subtournament. Specifically, we show that if a tournament *G* is “prime”—that is, if there is no subset , , such that for all , either for all or for all —then *G* is *U*_{5}-free if and only if either *G* is a specific tournament or can be partitioned into sets *X*, *Y*, *Z* such that , , and are transitive. From the prime *U*_{5}-free tournaments we can construct all the *U*_{5}-free tournaments. We use the theorem to show that every *U*_{5}-free tournament with *n* vertices has a transitive subtournament with at least vertices, and that this bound is tight.

A relational structure is (connected-) homogeneous if every isomorphism between finite (connected) substructures extends to an automorphism of the structure. We investigate notions that generalise (connected-) homogeneity, where ‘isomorphism’ may be replaced by ‘homomorphism’ or ‘monomorphism’ in the definition. In particular, we study the classes of finite connected-homomorphism-homogeneous graphs, with the aim of producing classifications. The main result is a classification of the finite graphs, where a graph *G* is if every homomorphism from a finite connected induced subgraph of *G* into *G* extends to an endomorphism of *G*. The finite (connected-homogeneous) graphs were classified by Gardiner in 1976, and from this we obtain classifications of the finite and finite graphs. Although not all the classes of finite connected-homomorphism-homogeneous graphs are completely characterised, we may still obtain the final hierarchy picture for these classes.

For an integer ℓ at least 3, we prove that if *G* is a graph containing no two vertex-disjoint circuits of length at least ℓ, then there is a set *X* of at most vertices that intersects all circuits of length at least ℓ. Our result improves the bound due to Birmelé, Bondy, and Reed (The Erdős–Pósa property for long circuits, Combinatorica 27 (2007), 135–145) who conjecture that ℓ vertices always suffice.

Tutte's 3-Flow Conjecture states that every 2-edge-connected graph with no 3-cuts admits a 3-flow. The 3-Flow Conjecture is equivalent to the following: let *G* be a 2-edge-connected graph, let *S* be a set of at most three vertices of *G*; if every 3-cut of *G* separates *S* then *G* has a 3-flow. We show that minimum counterexamples to the latter statement are 3-connected, cyclically 4-connected, and cyclically 7-edge-connected.

Deciding whether a digraph contains a pair of arc-disjoint in- and out-branchings rooted at a specified vertex is a well-known NP-complete problem (as proved by Thomassen, see ). This problem has been shown to be polynomial time solvable for semicomplete digraphs and for quasi-transitive digraphs . In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc-disjoint in- and out-branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from for semicomplete digraphs and solves an open problem from .

We study the following problem: given a real number *k* and an integer *d*, what is the smallest ε such that any fractional -precoloring of vertices at pairwise distances at least *d* of a fractionally *k*-colorable graph can be extended to a fractional -coloring of the whole graph? The exact values of ε were known for and any *d*. We determine the exact values of ε for if , and if , and give upper bounds for if , and if . Surprisingly, ε viewed as a function of *k* is discontinuous for all those values of *d*.