Petersen Cores and the Oddness of Cubic Graphs

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. We study lists by three 1‐factors, and call with a ‐core of G. If G is not 3‐edge‐colorable, then . In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if , then is an upper bound for the girth of G. We show that bounds the oddness of G as well. We prove that . If , then every ‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with . On the other hand, the difference between and can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer , there exists a bridgeless cubic graph G such that .     

The Game Saturation Number of a Graph

Given a family and a host graph H, a graph is ‐saturated relative to H if no subgraph of G lies in but adding any edge from to G creates such a subgraph. In the ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in , until G becomes ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts). Let denote the family of odd cycles and the family of n‐vertex trees, and write F for when . Our results include , for , for , and for . We also determine ; with , it is n when n is even, m when n is odd and m is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the P₄‐saturation game on .     

A Hypercube Variant with Small Diameter

This article introduces a new variant of hypercubes . The n‐dimensional twisted hypercube is obtained from two copies of the ‐dimensional twisted hypercube by adding a perfect matching between the vertices of these two copies of . We prove that the n‐dimensional twisted hypercube has diameter . This improves on the previous known variants of hypercube of dimension n and is optimal up to an error of order . Another type of hypercube variant that has similar structure and properties as is also discussed in the last section.     

The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and , which has the most complete subgraphs of size t, for . The conjectured extremal graph is , where with . Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when , and also reduced the general conjecture to the case . We prove the conjecture for and also establish a weaker form of the conjecture for all r.     

Saturation Numbers in Tripartite Graphs

Given graphs H and F, a subgraph is an F‐saturated subgraph of H if , but for all . The saturation number of F in H, denoted , is the minimum number of edges in an F‐saturated subgraph of H. In this article, we study saturation numbers of tripartite graphs in tripartite graphs. For and n₁, n₂, and n₃ sufficiently large, we determine and exactly and within an additive constant. We also include general constructions of ‐saturated subgraphs of with few edges for .     

Matching Extension Missing Vertices and Edges in Triangulations of Surfaces

Let G be a 5‐connected triangulation of a surface Σ different from the sphere, and let be the Euler characteristic of Σ. Suppose that with even and M and N are two matchings in of sizes m and n respectively such that . It is shown that if the pairwise distance between any two elements of is at least five and the face‐width of the embedding of G in Σ is at least , then there is a perfect matching M₀ in containing M such that .     

A Note on the Order of Iterated Line Digraphs

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices of the k‐iterated line digraph , for , where . We obtain this result by using the minimal polynomial of a quotient digraph of G.     

On the Existence of Tree Backbones that Realize the Chromatic Number on a Backbone Coloring

A proper k‐coloring of a graph is a function such that , for every . The chromatic number is the minimum k such that there exists a proper k‐coloring of G. Given a spanning subgraph H of G, a q‐backbone k‐coloring of is a proper k‐coloring c of such that , for every edge . The q‐backbone chromatic number is the smallest k for which there exists a q‐backbone k‐coloring of . In this work, we show that every connected graph G has a spanning tree T such that , and that this value is the best possible. As a direct consequence, we get that every connected graph G has a spanning tree T for which , if , or , otherwise. Thus, by applying the Four Color Theorem, we have that every connected nonbipartite planar graph G has a spanning tree T such that . This settles a question by Wang, Bu, Montassier, and Raspaud (J Combin Optim 23(1) (2012), 79–93), and generalizes a number of previous partial results to their question.     

Subcubic Edge‐Chromatic Critical Graphs Have Many Edges

We consider graphs G with such that and for every edge e, so‐called critical graphs. Jakobsen noted that the Petersen graph with a vertex deleted, , is such a graph and has average degree only . He showed that every critical graph has average degree at least , and asked if is the only graph where equality holds. A result of Cariolaro and Cariolaro shows that this is true. We strengthen this average degree bound further. Our main result is that if G is a subcubic critical graph other than , then G has average degree at least . This bound is best possible, as shown by the Hajós join of two copies of .     

Unique Colorability and Clique Minors

For a graph G, let denote the largest k such that G has k pairwise disjoint pairwise adjacent connected nonempty subgraphs, and let denote the largest k such that G has k pairwise disjoint pairwise adjacent connected subgraphs of size 1 or 2. Hadwiger 's conjecture states that , where is the chromatic number of G. Seymour conjectured for all graphs without antitriangles, that is,  three pairwise nonadjacent vertices. Here we concentrate on graphs G with exactly one ‐coloring. We prove generalizations of the following statements: (i) if and G has exactly one ‐coloring then , where the proof does not use the four‐color‐theorem, and (ii) if G has no antitriangles and G has exactly one ‐coloring then .     

Characterization of Digraphic Sequences with Strongly Connected Realizations

Let be a sequence of of nonnegative integers pairs. If a digraph D with satisfies and for each i with , then d is called a degree sequence of D. If D is a strict digraph, then d is called a strict digraphic sequence. Let be the collection of digraphs with degree sequence d . We characterize strict digraphic sequences d for which there exists a strict strong digraph .     

Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs

For any graph G, let be the number of spanning trees of G, be the line graph of G, and for any nonnegative integer r, be the graph obtained from G by replacing each edge e by a path of length connecting the two ends of e. In this article, we obtain an expression for in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if G is of order and size in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on for such a graph G.     

(1, k)‐Coloring of Graphs with Girth at Least Five on a Surface

A graph is ‐colorable if its vertex set can be partitioned into r sets so that the maximum degree of the graph induced by is at most for each . For a given pair , the question of determining the minimum such that planar graphs with girth at least g are ‐colorable has attracted much interest. The finiteness of was known for all cases except when . Montassier and Ochem explicitly asked if d₂(5, 1) is finite. We answer this question in the affirmative with ; namely, we prove that all planar graphs with girth at least five are (1, 10)‐colorable. Moreover, our proof extends to the statement that for any surface S of Euler genus γ, there exists a where graphs with girth at least five that are embeddable on S are (1, K)‐colorable. On the other hand, there is no finite k where planar graphs (and thus embeddable on any surface) with girth at least five are (0, k)‐colorable.     

On Crossing Numbers of Complete Tripartite and Balanced Complete Multipartite Graphs

The crossing number cr(G) of a graph G is the minimum number of crossings in a drawing of G in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of G is the minimum number of crossings in a such drawing of G with edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound to and prove . We also show that for n large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete r‐partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed r and the balanced complete r‐partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.     

Even Embeddings of the Complete Graphs and Their Cycle Parities

The complete graph on n vertices can be quadrangularly embedded on an orientable (resp. nonorientable) closed surface F² with Euler characteristic if and only if (resp. and ). In this article, we shall show that if quadrangulates a closed surface F², then has a quadrangular embedding on F² so that the length of each closed walk in the embedding has the parity specified by any given homomorphism , called the cycle parity.     

List‐Coloring the Squares of Planar Graphs without 4‐Cycles and 5‐Cycles

Let G be a planar graph without 4‐cycles and 5‐cycles and with maximum degree . We prove that . For arbitrarily large maximum degree Δ, there exist planar graphs of girth 6 with . Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to online list‐coloring. In addition, we prove bounds for ‐labeling. Specifically, and, more generally, , for positive integers p and q with . Again, these bounds come from a greedy coloring, so they immediately extend to the list‐coloring and online list‐coloring variants of this problem.     

Jacobsthal Numbers in Generalized Petersen Graphs

We prove that the number of 1‐factorizations of a generalized Petersen graph of the type is equal to the kth Jacobsthal number when k is odd, and equal to when k is even. Moreover, we verify the list coloring conjecture for .     

Extracting List Colorings from Large Independent Sets

We take an application of the Kernel Lemma by Kostochka and Yancey [11] to its logical conclusion. The consequence is a sort of magical way to draw conclusions about list coloring (and online list coloring) just from the existence of an independent set incident to many edges. We use this to prove an Ore‐degree version of Brooks' Theorem for online list‐coloring. The Ore‐degree of an edge in a graph G is . The Ore‐degree of G is . We show that every graph with and is online ‐choosable. In addition, we prove an upper bound for online list‐coloring triangle‐free graphs: . Finally, we characterize Gallai trees as the connected graphs G with no independent set incident to at least edges.     

Amalgams and χ‐Boundedness

A class of graphs is hereditary if it is closed under isomorphism and induced subgraphs. A class of graphs is χ‐bounded if there exists a function such that for all graphs , and all induced subgraphs H of G, we have that . We prove that proper homogeneous sets, clique‐cutsets, and amalgams together preserve χ‐boundedness. More precisely, we show that if and are hereditary classes of graphs such that is χ‐bounded, and such that every graph in either belongs to or admits a proper homogeneous set, a clique‐cutset, or an amalgam, then the class is χ‐bounded. This generalizes a result of [J Combin Theory Ser B 103(5) (2013), 567–586], which states that proper homogeneous sets and clique‐cutsets together preserve χ‐boundedness, as well as a result of [European J Combin 33(4) (2012), 679–683], which states that 1‐joins preserve χ‐boundedness. The house is the complement of the four‐edge path. As an application of our result and of the decomposition theorem for “cap‐free” graphs from [J Graph Theory 30(4) (1999), 289–308], we obtain that if G is a graph that does not contain any subdivision of the house as an induced subgraph, then .     

On the Probability that a Random Subgraph Contains a Circuit

Let and . We show that, if G is a sufficiently large simple graph of average degree at least μ, and H is a random spanning subgraph of G formed by including each edge independently with probability , then H contains a cycle with probability at least .