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 .     

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 .     

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 .     

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.     

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.     

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.     

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 .     

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.     

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 .     

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 .     

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.     

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 .     

Cayley Graphs of Diameter Two from Difference Sets

Let and be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree d and diameter k. When , it is well known that with equality if and only if the graph is a Moore graph. In the abelian case, we have . The best currently lower bound on is for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that for sufficiently large d and if , and m is odd.     

Forbidden Pairs of Disconnected Graphs Implying Hamiltonicity

Let H be a given graph. A graph G is said to be H‐free if G contains no induced copies of H. For a class of graphs, the graph G is ‐free if G is H‐free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2‐connected ‐free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non‐hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n₀ such that every 2‐connected ‐free graph of order at least n₀ is hamiltonian.     

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 .     

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.     

On the Neighbor Sum Distinguishing Index of Planar Graphs

Let c be a proper edge coloring of a graph with integers . Then , while Vizing's theorem guarantees that we can take . On the course of investigating irregularities in graphs, it has been conjectured that with only slightly larger k, that is, , we could enforce an additional strong feature of c, namely that it attributes distinct sums of incident colors to adjacent vertices in G if only this graph has no isolated edges and is not isomorphic to C₅. We prove the conjecture is valid for planar graphs of sufficiently large maximum degree. In fact an even stronger statement holds, as the necessary number of colors stemming from the result of Vizing is proved to be sufficient for this family of graphs. Specifically, our main result states that every planar graph G of maximum degree at least 28, which contains no isolated edges admits a proper edge coloring such that for every edge of G.     

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 .     

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.     

Partial Online List Coloring of Graphs

For a graph G, let be the maximum number of vertices of G that can be colored whenever each vertex of G is given t permissible colors. Albertson, Grossman, and Haas conjectured that if G is s‐choosable and , then . In this article, we consider the online version of this conjecture. Let be the maximum number of vertices of G that can be colored online whenever each vertex of G is given t permissible colors online. An analog of the above conjecture is the following: if G is online s‐choosable and then . This article generalizes some results concerning partial list coloring to online partial list coloring. We prove that for any positive integers , . As a consequence, if s is a multiple of t, then . We also prove that if G is online s‐choosable and , then and for any , .