A perfect matching covering of a graph *G* is a set of perfect matchings of *G* such that every edge of *G* is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of *G*). A cubic graph *G* is called a Kotzig graph if *G* has a 3-edge-coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex *w* of a cubic graph *G* such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then *G* has a Berge covering. We also obtain some results concerning the so-called 5-even subgraph double cover conjecture.

A *clique covering* of a simple graph *G* is a collection of cliques of *G* covering all the edges of *G* such that each vertex is contained in at most *k* cliques. The smallest *k* for which *G* admits a clique covering is called the local clique cover number of *G* and is denoted by lcc(*G*). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well-known problems are discussed. In particular, it is proved that the local clique cover number of every claw-free graph is at most , where Δ is the maximum degree of the graph and *c* is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw-free graph on *n* vertices with the minimum degree δ, is at most , where *c* is a constant.

A star edge coloring of a graph is a proper edge coloring without bichromatic paths and cycles of length four. In this article, we establish tight upper bounds for trees and subcubic outerplanar graphs, and derive an upper bound for outerplanar graphs.

Let *G* be a graph with vertex set and let be a set function associated with *G*. An *H*-factor of graph *G* is a spanning subgraphs *F* such that

Let be an even integer-valued function such that and let for . In this article, we investigate -factors of graphs by using Lovász's structural descriptions. Let denote the number of odd components of *G*. We show that if one of the following conditions holds, then *G* contains an -factor.

- (i)is even and for all ;
- (ii)is odd, for all and for all .

As a corollary, we show that if a graph *G* of odd order with minimum degree at least satisfies

then *G* contains an -factor, where . In particular, we make progress on the characterization problem for a special family of graphs proposed by Akiyama and Kano.

A set *S* of vertices in a graph *G* is an independent dominating set of *G* if *S* is an independent set and every vertex not in *S* is adjacent to a vertex in *S*. The independent domination number of *G*, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order *n* that does not have a subgraph isomorphic to *K*_{2, 3}, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if *G* is a cubic graph of order *n*, then , where denotes the domination number of *G*.

A graph *G* is equimatchable if each matching in *G* is a subset of a maximum-size matching and it is factor critical if has a perfect matching for each vertex *v* of *G*. It is known that any 2-connected equimatchable graph is either bipartite or factor critical. We prove that for 2-connected factor-critical equimatchable graph *G* the graph is either or for some *n* for any vertex *v* of *G* and any minimal matching *M* such that is a component of . We use this result to improve the upper bounds on the maximum number of vertices of 2-connected equimatchable factor-critical graphs embeddable in the orientable surface of genus *g* to if and to if . Moreover, for any nonnegative integer *g* we construct a 2-connected equimatchable factor-critical graph with genus *g* and more than vertices, which establishes that the maximum size of such graphs is . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers *g*, *h*, and *k* we provide a construction of arbitrarily large 2-connected equimatchable bipartite graphs with orientable genus *g*, respectively nonorientable genus *h*, and a genus embedding with face-width *k*. Finally, we prove that any *d*-degenerate 2-connected equimatchable factor-critical graph has at most vertices, where a graph is *d*-degenerate if every its induced subgraph contains a vertex of degree at most *d*.

Following problems posed by Gyárfás 2011, we show that for every *r*-edge-colouring of there is a monochromatic triple star of order at least , improving Ruszinkó's result 2012. An edge colouring of a graph is called a local *r*-colouring if every vertex spans edges of at most *r* distinct colours. We prove the existence of a monochromatic triple star with at least vertices in every local *r*-colouring of .

In 1998 the second author proved that there is an such that every graph satisfies . The first author recently proved that any graph satisfying contains a stable set intersecting every maximum clique. In this note, we exploit the latter result to give a much shorter, simpler proof of the former. Working from first principles, we omit only some five pages of proofs of known intermediate results (which appear in an extended version of this paper), and the proofs of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality.

Let and denote the second largest eigenvalue and the maximum number of edge-disjoint spanning trees of a graph *G*, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph *G* and bounds of , Cioabă and Wong conjectured that for any integers and a *d*-regular graph *G*, if , then . They proved the conjecture for , and presented evidence for the cases when . Thus the conjecture remains open for . We propose a more general conjecture that for a graph *G* with minimum degree , if , then . In this article, we prove that for a graph *G* with minimum degree δ, each of the following holds.

- (i)For , if and , then .
- (ii)For , if and , then .

Our results sharpen theorems of Cioabă and Wong and give a partial solution to Cioabă and Wong's conjecture and Seymour's problem. We also prove that for a graph *G* with minimum degree , if , then the edge connectivity is at least *k*, which generalizes a former result of Cioabă. As corollaries, we investigate the Laplacian and signless Laplacian eigenvalue conditions on and edge connectivity.

Given an edge coloring of a graph with a set of *m* colors, we say that the graph is *exactly m-colored* if each of the colors is used. In 1999, Stacey and Weidl, partially resolving a conjecture of Erickson from 1994, showed that for a fixed natural number and for all sufficiently large *k*, there is a *k*-coloring of the complete graph on such that no complete infinite subgraph is exactly *m*-colored. In the light of this result, we consider the question of how close we can come to finding an exactly *m*-colored complete infinite subgraph. We show that for a natural number *m* and any finite coloring of the edges of the complete graph on with *m* or more colors, there is an exactly -colored complete infinite subgraph for some satisfying ; this is best possible up to the additive constant. We also obtain analogous results for this problem in the setting of *r*-uniform hypergraphs. Along the way, we also prove a recent conjecture of the second author and investigate generalizations of this conjecture to *r*-uniform hypergraphs.

Let *G* be a graph whose edges are colored with *k* colors, and be a *k*-tuple of graphs. A *monochromatic* -*decomposition* of *G* is a partition of the edge set of *G* such that each part is either a single edge or forms a monochromatic copy of in color *i*, for some . Let be the smallest number ϕ, such that, for every order-*n* graph and every *k*-edge-coloring, there is a monochromatic -decomposition with at most ϕ elements. Extending the previous results of Liu and Sousa [Monochromatic -decompositions of graphs, *J Graph Theory* 76 (2014), 89–100], we solve this problem when each graph in is a clique and is sufficiently large.

Consider a simple graph and its *proper* edge coloring *c* with the elements of the set . We say that *c* is *neighbor set distinguishing* (or *adjacent strong*) if for every edge , the set of colors incident with *u* is distinct from the set of colors incident with *v*. Let us then consider a stronger requirement and suppose we wish to distinguishing adjacent vertices by sums of their incident colors. In both problems the challenging conjectures presume that such colorings exist for any graph *G* containing no isolated edges if only . We prove that in both problems is sufficient. The proof is based on the Combinatorial Nullstellensatz, applied in the “sum environment.” In fact the identical bound also holds if we use any set of *k* real numbers instead of as edge colors, and the same is true in list versions of the both concepts. In particular, we therefore obtain that lists of length ( in fact) are sufficient for planar graphs.

We collect some of our favorite proofs of Brooks' Theorem, highlighting advantages and extensions of each. The proofs illustrate some of the major techniques in graph coloring, such as greedy coloring, Kempe chains, hitting sets, and the Kernel Lemma. We also discuss standard strengthenings of vertex coloring, such as list coloring, online list coloring, and Alon–Tarsi orientations, since analogs of Brooks' Theorem hold in each context. We conclude with two conjectures along the lines of Brooks' Theorem that are much stronger, the Borodin–Kostochka Conjecture and Reed's Conjecture.

A classical theorem of Brooks in graph coloring theory states that every connected graph *G* has its chromatic number less than or equal to its maximum degree , unless *G* is a complete graph or an odd cycle in which case is equal to . Brooks' theorem has been extended to list colorings by Erdős, Rubin, and Taylor (and, independently, by Vizing) and to some of their variants such as list *T*-colorings and pair-list colorings. The bichromatic number is a relatively new parameter arisen in the study of extremal hereditary properties of graphs. This parameter simultaneously generalizes the chromatic number and the clique covering number of a graph.

In this article, we prove a theorem, akin to that of Brooks, which states that every graph *G* has its bichromatic number less than or equal to its bidegree , unless *G* belongs to a set of specified graphs in which case is equal to .

In this short note, we extend the result of Galluccio, Goddyn, and Hell, which states that graphs of large girth excluding a minor are nearly bipartite. We also prove a similar result for the oriented chromatic number, from which follows in particular that graphs of large girth excluding a minor have oriented chromatic number at most 5, and for the *p*th chromatic number , from which follows in particular that graphs *G* of large girth excluding a minor have .

Richter and Thomassen proved that every graph has an edge *e* such that the crossing number of is at least . Fox and Cs. Tóth proved that dense graphs have large sets of edges (proportional in the total number of edges) whose removal leaves a graph with crossing number proportional to the crossing number of the original graph; this result was later strenghthened by Černý, Kynčl, and G. Tóth. These results make our understanding of the decay of crossing numbers in dense graphs essentially complete. In this article we prove a similar result for large sparse graphs in which the number of edges is not artificially inflated by operations such as edge subdivisions. We also discuss the connection between the decay of crossing numbers and expected crossing numbers, a concept recently introduced by Mohar and Tamon.

A proper edge coloring of a graph with colors 1, 2, 3, … is called an interval coloring if the colors on the edges incident to each vertex form an interval of integers. A bipartite graph is -biregular if every vertex in one part has degree *a* and every vertex in the other part has degree *b*. It has been conjectured that all such graphs have interval colorings. We prove that all (3, 6)-biregular graphs have interval colorings and that all (3, 9)-biregular graphs having a cubic subgraph covering all vertices of degree 9 admit interval colorings. Moreover, we prove that slightly weaker versions of the conjecture hold for (3, 5)-biregular, (4, 6)-biregular, and (4, 8)-biregular graphs. All our proofs are constructive and yield polynomial time algorithms for constructing the required colorings.

Thomassen proved that every -connected graph *G* contains an induced cycle *C* such that is *k*-connected, establishing a conjecture of Lovász. In general, one could ask the following question: For any positive integers , does there exist a smallest positive integer such that for any -connected graph *G*, any with , and any , there is an induced cycle *C* in such that and is *l*-connected? The case when is a well-known conjecture of Lovász that is still open for . In this article, we prove and . We also consider a weaker version: For any positive integers , is there a smallest positive integer such that for every -connected graph *G* and any with , there is an induced cycle *C* in such that is *l*-connected? The case when was studied by Thomassen. We prove and .

This work brings together ideas of mixing graph colorings, discrete homotopy, and precoloring extension. A particular focus is circular colorings. We prove that all the -colorings of a graph *G* can be obtained by successively recoloring a single vertex provided along the lines of Cereceda, van den Heuvel, and Johnson's result for *k*-colorings. We give various bounds for such mixing results and discuss their sharpness, including cases where the bounds for circular and classical colorings coincide. As a corollary, we obtain an Albertson-type extension theorem for -precolorings of circular cliques. Such a result was first conjectured by Albertson and West. General results on homomorphism mixing are presented, including a characterization of graphs *G* for which the endomorphism monoid can be generated through the mixing process. As in similar work of Brightwell and Winkler, the concept of dismantlability plays a key role.

In this article, we continue the study of 2-colorings in hypergraphs. A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. Let denote the class of all *k*-uniform *k*-regular hypergraphs. It is known (see Alon and Bregman [Graphs Combin. 4 (1988) 303–306] and Thomassen [J. Amer. Math. Soc. 5 (1992), 217–229] that every hypergraph is 2-colorable, provided . As remarked by Alon and Bregman the result is not true when , as may be seen by considering the Fano plane. Indeed there are several constructions for building infinite families of hypergraphs in that are not 2-colorable. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set *X* of vertices in a hypergraph *H* to be a free set in *H* if we can 2-color such that every edge in *H* receives at least one vertex of each color. We conjecture that for , every hypergraph has a free set of size in *H*. We show that the bound cannot be improved for any and we prove our conjecture when . Our proofs use results from areas such as transversal in hypergraphs, cycles in digraphs, and probabilistic arguments.

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2-connected graphs, that are not 3-connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2-connected graphs to *k*-connected graphs for any *k*, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and *k*-CS-transitive graphs.

Let *G* be a planar triangle-free graph and let *C* be a cycle in *G* of length at most 8. We characterize all situations where a 3-coloring of *C* does not extend to a proper 3-coloring of the whole graph.

A strong edge coloring of a graph is an assignment of colors to the edges of the graph such that for every color, the set of edges that are given that color form an induced matching in the graph. The strong chromatic index of a graph *G*, denoted by , is the minimum number of colors needed in any strong edge coloring of *G*. A graph is said to be *chordless* if there is no cycle in the graph that has a chord. Faudree, Gyárfás, Schelp, and Tuza (The Strong Chromatic Index of Graphs, Ars Combin 29B (1990), 205–211) considered a particular subclass of chordless graphs, namely, the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan (Strong Chromatic Index of 2-degenerate Graphs, J Graph Theory, 73(2) (2013), 119–126) answered this question in the affirmative by proving that if *G* is a chordless graph with maximum degree Δ, then . We improve this result by showing that for every chordless graph *G* with maximum degree Δ, . This bound is tight up to an additive constant.

We prove that the vertex degree threshold for tiling (the 3-uniform hypergraph with four vertices and two triples) in a 3-uniform hypergraph on vertices is , where if and otherwise. This result is best possible, and is one of the first results on vertex degree conditions for hypergraph tiling.

Sheehan's Conjecture states that every hamiltonian 4-regular graph possesses a second Hamilton cycle. In this article, we verify Sheehan's Conjecture for 4-regular graphs of order *n* whose automorphism group has size at least if either for all , or for and *m* is either an odd prime or a power of 2. We also give lower bounds on the size of the automorphism group and degree of a regular hamiltonian graph that guarantee existence of a second Hamilton cycle.

Let denote the number of convex cycles of a simple graph *G* of order *n*, size *m*, and girth . It is proved that and that equality holds if and only if *G* is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.

We study minimum degree conditions for which a graph with given odd girth has a simple structure. For example, the classical work of Andrásfai, Erdős, and Sós implies that every *n*-vertex graph with odd girth and minimum degree bigger than must be bipartite. We consider graphs with a weaker condition on the minimum degree. Generalizing results of Häggkvist and of Häggkvist and Jin for the cases and 3, we show that every *n*-vertex graph with odd girth and minimum degree bigger than is homomorphic to the cycle of length . This is best possible in the sense that there are graphs with minimum degree and odd girth that are not homomorphic to the cycle of length . Similar results were obtained by Brandt and Ribe-Baumann.

We classify noncomplete prime valency graphs satisfying the property that their automorphism group is transitive on both the set of arcs and the set of 2-geodesics. We prove that either Γ is 2-arc transitive or the valency *p* satisfies , and for each such prime there is a unique graph with this property: it is a nonbipartite antipodal double cover of the complete graph with automorphism group and diameter 3.

An antimagic labeling of a graph *G* with *m* edges is a bijection from to such that for all vertices *u* and *v*, the sum of labels on edges incident to *u* differs from that for edges incident to *v*. Hartsfield and Ringel conjectured that every connected graph other than the single edge *K*_{2} has an antimagic labeling. We prove this conjecture for regular graphs of odd degree.

We prove that for all an interval graph is -Hamilton-connected if and only if its scattering number is at most *k*. This complements a previously known fact that an interval graph has a nonnegative scattering number if and only if it contains a Hamilton cycle, as well as a characterization of interval graphs with positive scattering numbers in terms of the minimum size of a path cover. We also give an time algorithm for computing the scattering number of an interval graph with *n* vertices and *m* edges, which improves the previously best-known time bound for solving this problem. As a consequence of our two results, the maximum *k* for which an interval graph is *k*-Hamilton-connected can be computed in time.

The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here, we consider oriented graphs. We show the existence of a graph where the directed local chromatic number of all oriented versions of the graph is strictly less than the local chromatic number of the underlying undirected graph. We show that for fractional versions the analogous problem has a different answer: there always exists an orientation for which the directed and undirected values coincide. We also determine the supremum of the possible ratios of these fractional parameters, which turns out to be *e*, the basis of the natural logarithm.

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 .

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.

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.

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.

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.

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.

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.

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.