The Images of the Clique Operator and Its Square are Different

Let be the class of all graphs and K be the clique operator. The validity of the equality has been an open question for several years. A graph in but not in is exhibited here.     

On the Iterated Biclique Operator

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. The biclique graph of G, denoted by , is the intersection graph of the bicliques of G. We say that a graph G diverges (or converges or is periodic) under an operator F whenever ( for some m, or for some k and , respectively). Given a graph G, the iterated biclique graph of G, denoted by , is the graph obtained by applying the biclique operator k successive times to G. In this article, we study the iterated biclique graph of G. In particular, we classify the different behaviors of when the number of iterations k grows to infinity. That is, we prove that a graph either diverges or converges under the biclique operator. We give a forbidden structure characterization of convergent graphs, which yield a polynomial time algorithm to decide if a given graph diverges or converges. This is in sharp contrast with the situsation for the better known clique operator, where it is not even known if the corresponding problem is decidable. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 181–190, 2013     

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 .     

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 .     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

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.     

Equimatchable Graphs on Surfaces

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.     

A Note on Hitting Maximum and Maximal Cliques With a Stable Set

It was recently proved that any graph satisfying contains a stable set hitting every maximum clique. In this note, we prove that the same is true for graphs satisfying unless the graph is the strong product of an odd hole and .We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.     

Average Degree in Graph Powers

The kth power of a simple graph G, denoted by , is the graph with vertex set where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of . Here we prove that if G is connected with minimum degree and , then G⁴ has average degree at least . We also prove that if G is a connected d‐regular graph on n vertices with diameter at least , then the average degree of is at least Both these results are shown to be essentially best possible; the second is best possible even when is arbitrarily large.     

Cycle‐Saturated Graphs with Minimum Number of Edges

A graph G is called H‐saturated if it does not contain any copy of H, but for any edge e in the complement of G, the graph contains some H. The minimum size of an n‐vertex H‐saturated graph is denoted by . We prove holds for all , where is a cycle with length k. A graph G is H‐semisaturated if contains more copies of H than G does for . Let be the minimum size of an n‐vertex H‐semisaturated graph. We have We conjecture that our constructions are optimal for . © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 203–215, 2013     

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 .     

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.     

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.     

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

Maximizing H‐Colorings of a Regular Graph

For graphs G and H, a homomorphism from G to H, or H‐coloring of G, is an adjacency preserving map from the vertex set of G to the vertex set of H. Our concern in this article is the maximum number of H‐colorings admitted by an n‐vertex, d‐regular graph, for each H. Specifically, writing for the number of H‐colorings admitted by G, we conjecture that for any simple finite graph H (perhaps with loops) and any simple finite n‐vertex, d‐regular, loopless graph G, we have where is the complete bipartite graph with d vertices in each partition class, and is the complete graph on vertices.Results of Zhao confirm this conjecture for some choices of H for which the maximum is achieved by . Here, we exhibit for the first time infinitely many nontrivial triples for which the conjecture is true and for which the maximum is achieved by .We also give sharp estimates for and in terms of some structural parameters of H. This allows us to characterize those H for which is eventually (for all sufficiently large d) larger than and those for which it is eventually smaller, and to show that this dichotomy covers all nontrivial H. Our estimates also allow us to obtain asymptotic evidence for the conjecture in the following form. For fixed H, for all d‐regular G, we have where as . More precise results are obtained in some special cases.     

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.     

Toughness and Vertex Degrees

We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is t‐tough. We first give a best monotone theorem when , but then show that for any integer , a best monotone theorem for requires at least nonredundant conditions, where grows superpolynomially as . When , we give an additional, simple theorem for G to be t‐tough, in terms of its vertex degrees.     

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 .     

Counterexamples to the List Square Coloring Conjecture

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