There are numerous results bounding the circumference of certain 3-connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3-connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer *k*, there is an integer such that every 3-connected graph with at least *n* vertices contains a - or -minor. This result implies that the size of the largest bond in a 3-connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3-connected graph by showing that any 3-connected graph on *n* vertices has a bond of size at least . In addition, we show the following: Let *G* be a 3-connected planar or cubic graph on *n* vertices. Then for any , *G* has a -minor with , and thus a bond of size at least .

We prove that every digraph of circumference *l* has DAG-width at most *l*. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).^{1} As a consequence of this result we deduce that the *k*-linkage problem is polynomially solvable for every fixed *k* in the class of digraphs with bounded circumference. This answers a question posed in J. Bang-Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283–303). We also prove that the weak *k*-linkage problem (where we ask for arc-disjoint paths) is polynomially solvable for every fixed *k* in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP-hard on digraphs of DAG-width at most 5.

A spanning subgraph *F* of a graph *G* is called *perfect* if *F* is a forest, the degree of each vertex *x* in *F* is odd, and each tree of *F* is an induced subgraph of *G*. We provide a short linear-algebraic proof of the following theorem of A. D. Scott (Graphs Combin 17 (2001), 539–553): A connected graph *G* contains a perfect forest if and only if *G* has an even number of vertices.

We characterize the quartic (i.e., 4-regular) multigraphs with the property that every edge lies in a triangle. The main result is that such graphs are either squares of cycles, line multigraphs of cubic multigraphs, or are obtained from these by a number of simple subgraph-replacement operations. A corollary of this is that a simple quartic graph with every edge in a triangle is either the square of a cycle, the line graph of a cubic graph or a graph obtained from the line multigraph of a cubic multigraph by replacing triangles with copies of *K*_{1, 1, 3}.

The clique number of an undirected graph *G* is the maximum order of a complete subgraph of *G* and is a well-known lower bound for the chromatic number of *G*. Every proper *k*-coloring of *G* may be viewed as a homomorphism (an edge-preserving vertex mapping) of *G* to the complete graph of order *k*. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth *k* for all .

Let *H* denote the tree with six vertices, two of which are adjacent and of degree 3. Let *G* be a graph and be distinct vertices of *G*. We characterize those *G* that contain a topological *H* in which are of degree 3 and are of degree 1, which include all 5-connected graphs. This work was motivated by the Kelmans–Seymour conjecture that 5-connected nonplanar graphs contain topological *K*_{5}.

Determining the maximum number of edges in an *n*-vertex *C*_{4}-free graph is a well-studied problem that dates back to a paper of Erdős from 1938. One of the most important families of *C*_{4}-free graphs are the Erdős-Rényi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose-Chowla Sidon set is isomorphic to a large induced subgraph of the Erdős-Rényi orthogonal polarity graph. Using this isomorphism, we prove that the Petersen graph is a subgraph of every sufficiently large Erdős-Rényi orthogonal polarity graph.

We seek the maximum number of colors in an edge-coloring of the complete graph not having *t* edge-disjoint rainbow spanning subgraphs of specified types. Let , , and denote the answers when the spanning subgraphs are cycles, matchings, or trees, respectively. We prove for and for . We prove for and for . We also provide constructions for the more general problem in which colorings are restricted so that colors do not appear on more than *q* edges at a vertex.

Let *B* be a positive integer and let *G* be a simple graph. An excessive [*B*]-factorization of *G* is a minimum set of matchings, each of size *B*, whose union is . The number of matchings in an excessive [*B*]-factorization of *G* (or ∞ if an excessive [*B*]-factorization does not exist) is a graph parameter called the *excessive* [*B*]-*index* of *G* and denoted by . In this article we prove that, for any fixed value of *B*, the parameter can be computed in polynomial time in the size of the graph *G*. This solves a problem posed by one of the authors at the 21st British Combinatorial Conference.

Given a graph *G* of order *n*, the σ-*polynomial* of *G* is the generating function where is the number of partitions of the vertex set of *G* into *i* nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti (Trans Am Math Soc 332 (1992), 729–756) proved that σ-polynomials of graphs with chromatic number at least had all real roots, and conjectured the same held for chromatic number . We affirm this conjecture.

In Aldred and Plummer (Discrete Math 197/198 (1999) 29–40) proved that every *m*-connected -free graph of even order has a perfect matching *M* with and , where *F*_{1} and *F*_{2} are prescribed disjoint sets of independent edges with and . It is known that if *l* satisfies , then the star-free condition in the above result is best possible. In this paper, for , we prove a refinement of the result in which the condition is replaced by the weaker condition that *G* is -free (note that the new condition does not depend on *l*). We also show that if *m* is even and either or , then for *m*-connected graphs *G* with sufficiently large order, one can replace the condition by the still weaker condition that *G* is -free. The star-free conditions in our results are best possible.

A graph *G* is -*colorable* if can be partitioned into two sets and so that the maximum degree of is at most *j* and of is at most *k*. While the problem of verifying whether a graph is (0, 0)-colorable is easy, the similar problem with in place of (0, 0) is NP-complete for all nonnegative *j* and *k* with . Let denote the supremum of all *x* such that for some constant every graph *G* with girth *g* and for every is -colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing *g* from 5 further on does not increase much. Our constructions show that for every *g*, . We also find exact values of for all *g* and all .

A *bi-subdivision* of a graph *J* is a graph *H* obtained from *J* by subdividing each of its edges by inserting an even number of vertices. A matching covered subgraph *H* of a matching covered graph *G* is *conformal* if has a perfect matching. Using the theory of ear decompositions, Lovász (Combinatorica, 3 (1983), 105–117) showed that every nonbipartite matching covered graph has a conformal subgraph which is either a bi-subdivision of *K*_{4} or of . (The graph is the triangular prism.) A matching covered graph is *K*_{4}-*based* if it contains a bi-subdivision of *K*_{4} as a conformal subgraph; otherwise it is *K*_{4}-*free*. -*based* and -*free*
graphs are analogously defined. The result of Lovász quoted above implies that any nonbipartite matching covered graph is either *K*_{4}-based or -based (or both). The problem of deciding which matching covered graphs are *K*_{4}-based and which are -based is, in general, unsolved. In this paper, we present a solution to this classification problem in the special case of planar graphs. In Section 2, we show that a matching covered graph is *K*_{4}-free (-free) if and only if each of its bricks is *K*_{4}-free (-free). In Section 5, we show that a planar brick is *K*_{4}-free if and only if it has precisely two odd faces. In Section 6, we determine the list of all -free planar bricks; apart from one exception, it consists of two infinite families of bricks. The principal tool we use for proving our results is the brick generation procedure established by Norine and Thomas (J Combin Theory Ser B, 97 (2007), 769–817).

Let *D* be a digraph and let be the arc-strong connectivity of *D*, and be the size of a maximum matching of *D*. We proved that if , then *D* has a spanning eulerian subdigraph.

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is *G*-symmetric if *G* is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by *G*, then Γ is an imprimitive *G*-symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.

We show that every *n*-vertex planar graph admits a simultaneous embedding without mapping and with fixed edges with any -vertex planar graph. In order to achieve this result, we prove that every *n*-vertex plane graph has an induced outerplane subgraph containing at least vertices. Also, we show that every *n*-vertex planar graph and every *n*-vertex planar partial 3-tree admit a simultaneous embedding without mapping and with fixed edges.

Consider a graph *G* on *n* vertices satisfying the following Ore-type condition: for any two nonadjacent vertices *x* and *y* of *G*, we have . We conjecture that if we color the edges of *G* with two colors then the vertex set of *G* can be partitioned to two vertex disjoint monochromatic cycles of distinct colors. In this article, we prove an asymptotic version of this conjecture.

We produce an edge-coloring of the complete 3-uniform hypergraph on *n* vertices with colors such that the edges spanned by every set of five vertices receive at least three distinct colors. This answers the first open case of a question of Conlon-Fox-Lee-Sudakov (Int Math Res Not, to appear) who asked whether such a coloring exists with colors.

The graph reconstruction conjecture asserts that every finite simple graph on at least three vertices can be reconstructed up to isomorphism from its deck—the collection of its vertex-deleted subgraphs. Kocay's Lemma is an important tool in graph reconstruction. Roughly speaking, given the deck of a graph *G* and any finite sequence of graphs, it gives a linear constraint that every reconstruction of *G* must satisfy. Let be the number of distinct (mutually nonisomorphic) graphs on *n* vertices, and let be the number of distinct decks that can be constructed from these graphs. Then the difference measures how many graphs cannot be reconstructed from their decks. In particular, the graph reconstruction conjecture is true for *n*-vertex graphs if and only if . We give a framework based on Kocay's lemma to study this discrepancy. We prove that if *M* is a matrix of covering numbers of graphs by sequences of graphs, then . In particular, all *n*-vertex graphs are reconstructible if one such matrix has rank . To complement this result, we prove that it is possible to choose a family of sequences of graphs such that the corresponding matrix *M* of covering numbers satisfies .

A graph *G* is *perfect* if for all induced subgraphs *H* of *G*, . A graph *G* is *Berge* if neither *G* nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew-partition.” A *clique-coloring* of a graph *G* is an assignment of colors to the vertices of *G* in such a way that no inclusion-wise maximal clique of *G* of size at least two is monochromatic, and the *clique-chromatic number* of *G*, denoted by , is the smallest number of colors needed to clique-color *G*. There exist graphs of arbitrarily large clique-chromatic number, but it is not known whether the clique-chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew-partition is 2-clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. (http://arxiv.org/abs/1308.6444).

In this article we consider minors of ribbon graphs (or, equivalently, cellularly embedded graphs). The theory of minors of ribbon graphs differs from that of graphs in that contracting loops is necessary and doing this can create additional vertices and components. Thus, the ribbon graph minor relation is incompatible with the graph minor relation. We discuss excluded minor characterizations of minor closed families of ribbon graphs. Our main result is an excluded minor characterization of the family of ribbon graphs that represent knot and link diagrams.

Given a graph and a colouring , the induced colour of a vertex *v* is the sum of the colours at the edges incident with *v*. If all the induced colours of vertices of *G* are distinct, the colouring is called antimagic. If *G* has a bijective antimagic colouring , the graph *G* is called antimagic. A conjecture of Hartsfield and Ringel states that all connected graphs other than *K*_{2} are antimagic. Alon, Kaplan, Lev, Roddity and Yuster proved this conjecture for graphs with minimum degree at least for some constant *c*; we improve on this result, proving the conjecture for graphs with average degree at least some constant *d*_{0}.

We develop a nonlinear spectral graph theory, in which the Laplace operator is replaced by the 1 − Laplacian Δ_{1}. The eigenvalue problem is to solve a nonlinear system involving a set valued function. In the study, we investigate the structure of the solutions, the minimax characterization of eigenvalues, the multiplicity theorem, etc. The eigenvalues as well as the eigenvectors are computed for several elementary graphs. The graphic feature of eigenvalues are also studied. In particular, Cheeger's constant, which has only some upper and lower bounds in linear spectral theory, equals to the first nonzero Δ_{1} eigenvalue for connected graphs.

An edge coloring of a graph is said to be an *r*-local coloring if the edges incident to any vertex are colored with at most *r* colors. Generalizing a result of Bessy and Thomassé, we prove that the vertex set of any 2-locally colored complete graph may be partitioned into two disjoint monochromatic cycles of different colors. Moreover, for any natural number *r*, we show that the vertex set of any *r*-locally colored complete graph may be partitioned into disjoint monochromatic cycles. This generalizes a result of Erdős, Gyárfás, and Pyber.

The global mean of subtrees of a tree is the average order (i.e., average number of vertices) of its subtrees. Analogously, the local mean of a vertex in a tree is the average order of subtrees containing this vertex. In the comprehensive study of these concepts by Jamison (J Combin Theory Ser B 35 (1983), 207–223 and J Combin Theory Ser B 37 (1984), 70–78), several open questions were proposed. One of them asks if the largest local mean always occurs at a leaf vertex. Another asks if it is true that the local mean of any vertex of any tree is at most twice the global mean. In this note, we answer the first question by showing that the largest local mean always occurs at a leaf or a vertex of degree 2 and that both cases are possible. With this result, a positive answer to the second question is provided. We also show some related results on local mean and global mean of trees.

The Ramsey numbers of cycles imply that every 2-edge-colored complete graph on *n* vertices contains monochromatic cycles of all lengths between 4 and at least . We generalize this result to colors by showing that every *k*-edge-colored complete graph on vertices contains -edge-colored cycles of all lengths between 3 and at least .

We study choosability with separation which is a constrained version of list coloring of graphs. A -*list assignment L* of a graph *G* is a function that assigns to each vertex *v* a list of at least *k* colors and for any adjacent pair , the lists and share at most *d* colors. A graph *G* is -choosable if there exists an *L*-coloring of *G* for every -list assignment *L*. This concept is also known as choosability with separation. We prove that planar graphs without 4-cycles are (3, 1)-choosable and that planar graphs without 5- and 6-cycles are (3, 1)-choosable. In addition, we give an alternative and slightly stronger proof that triangle-free planar graphs are (3, 1)-choosable.

A graph of order *n* is *p**-factor-critical*, where *p* is an integer of the same parity as *n*, if the removal of any set of *p* vertices results in a graph with a perfect matching. 1-factor-critical graphs and 2-factor-critical graphs are factor-critical graphs and bicritical graphs, respectively. It is well known that every connected vertex-transitive graph of odd order is factor-critical and every connected nonbipartite vertex-transitive graph of even order is bicritical. In this article, we show that a simple connected vertex-transitive graph of odd order at least five is 3-factor-critical if and only if it is not a cycle.

In this note we consider colorings of series-parallel graphs. Specifically, we provide bounds on their fractional and circular chromatic numbers and the defective version of these parameters. The main result is that the fractional chromatic number of any series-parallel graph of odd girth *k* is exactly .

We prove that the list chromatic index of a graph of maximum degree Δ and treewidth is Δ; and that the total chromatic number of a graph of maximum degree Δ and treewidth is . This improves results by Meeks and Scott.

We develop a new method for enumerating independent sets of a fixed size in general graphs, and we use this method to show that a conjecture of Engbers and Galvin [7] holds for all but finitely many graphs. We also use our method to prove special cases of a conjecture of Kahn [13]. In addition, we show that our method is particularly useful for computing the number of independent sets of small sizes in general regular graphs and Moore graphs, and we argue that it can be used in many other cases when dealing with graphs that have numerous structural restrictions.

Biregular -cages are graphs of girth *g* that contain vertices of degrees *r* and *m* and are of the smallest order among all such graphs. We show that for every and every odd , there exists an integer *m*_{0} such that for every *even* , the biregular -cage is of order equal to a natural lower bound analogous to the well-known Moore bound. In addition, when *r* is odd, the restriction on the parity of *m* can be removed, and there exists an integer *m*_{0} such that a biregular -cage of order equal to this lower bound exists *for all* . This is in stark contrast to the result classifying all cages of degree *k* and girth *g* whose order is equal to the Moore bound.

We introduce the concept of a signed circuit cover of a signed graph. A signed circuit cover is a natural analog of a circuit cover of a graph and is equivalent to a covering of the corresponding signed graphic matroid with circuits. As in the case of graphs, a signed graph has a signed circuit cover only when it admits a nowhere-zero integer flow. In the present article, we establish the existence of a universal coefficient such that every signed graph *G* that admits a nowhere-zero integer flow has a signed circuit cover of total length at most . We show that if *G* is bridgeless, then , and in the general case .

We study the local profiles of trees. We show that in contrast with the situation for general graphs, the limit set of *k*-profiles of trees is convex. We initiate a study of the defining inequalities of this convex set. Many challenging problems remain open.

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 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*.

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.

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.

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.

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.

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 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.