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.     

Minors in ‐ Chromatic Graphs,II

Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for .     

Cycles Avoiding a Color in Colorful Graphs

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 .     

On the Circular Chromatic Number of Graph Powers

This article intends to study some functors from the category of graphs to itself such that, for any graph G, the circular chromatic number of is determined by that of G. In this regard, we investigate some coloring properties of graph powers. We show that provided that . As a consequence, we show that if , then . In particular, and has no subgraph with circular chromatic number equal to . This provides a negative answer to a question asked in (X. Zhu, Discrete Math, 229(1–3) (2001), 371–410). Moreover, we investigate the nth multichromatic number of subdivision graphs. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that .     

Total Vertex Irregularity Strength of Dense Graphs

Consider a graph of minimum degree δ and order n. Its total vertex irregularity strength is the smallest integer k for which one can find a weighting such that for every pair of vertices of G. We prove that the total vertex irregularity strength of graphs with is bounded from above by . One of the cornerstones of the proof is a random ordering of the vertices generated by order statistics.     

On the Edit Distance from ‐Free Graphs

The edit distance between two graphs on the same vertex set is defined to be the size of the symmetric difference of their edge sets. The edit distance function of a hereditary property, , is a function of p, and measures, asymptotically, the furthest graph of edge density p from under this metric. In this article, we address the hereditary property , the property of having no induced copy of the complete bipartite graph with two vertices in one class and t in the other. Employing an assortment of techniques and colored regularity graph constructions, we are able to determine the edit distance function over the entire domain when and extend the interval over which the edit distance function for is known for all values of t, determining its maximum value for all odd t. We also prove that the function for odd t has a nontrivial interval on which it achieves its maximum. These are the only known principal hereditary properties for which this occurs. In the process of studying this class of functions, we encounter some surprising connections to extremal graph theory problems, such as strongly regular graphs and the problem of Zarankiewicz.     

Spanning Trees with Vertices Having Large Degrees

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.     

Anti‐Ramsey Problems for t Edge‐Disjoint Rainbow Spanning Subgraphs: Cycles,Matchings, or Trees

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.     

Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles

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.     

Interval Minors of Complete Bipartite Graphs

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in ‐interval minor‐free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of ‐interval minor‐free graphs is studied.     

Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

Two‐sided Group Digraphs and Graphs

We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets of a group G, we define the two‐sided group digraph to have vertex set G, and an arc from x to y if and only if for some and . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which may be viewed as a simple graph of valency , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8.     

Locally Symmetric Graphs of Girth 4

We classify the family of connected, locally symmetric graphs of girth 4 (finite and infinite). They are all regular, with the exception of the complete bipartite graph . There are, up to isomorphism, exactly four such k‐regular graphs for every , one for , two for , and exactly three for every infinite cardinal k. In the last paragraph, we consider locally symmetric graphs of girth >4.     

On Non‐Hamiltonian Graphs for which every Vertex‐Deleted Subgraph Is Traceable

We call a graph G a platypus if G is non‐hamiltonian, and for any vertex v in G, the graph is traceable. Every hypohamiltonian and every hypotraceable graph is a platypus, but there exist platypuses that are neither hypohamiltonian nor hypotraceable. Among other things, we give a sharp lower bound on the size of a platypus depending on its order, draw connections to other families of graphs, and solve two open problems of Wiener. We also prove that there exists a k‐connected platypus for every .     

Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited

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.     

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.     

Chordal 2‐Connected Graphs and Spanning Trees

We present a transformation on a chordal 2‐connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with , the threshold graph having n vertices and m edges that consists of an ‐clique and vertices of degree 2 is the only graph with the fewest spanning trees among all 2‐connected chordal graphs on n vertices and m edges.     

Graphs Containing Topological H

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

Biembedding a Steiner Triple System With a Hamilton Cycle Decomposition of a Complete Graph

We construct a face two‐colourable, blue and green say, embedding of the complete graph in a nonorientable surface in which there are blue faces each of which have a hamilton cycle as their facial walk and green faces each of which have a triangle as their facial walk; equivalently a biembedding of a Steiner triple system of order n with a hamilton cycle decomposition of , for all and . Using a variant of this construction, we establish the minimum genus of nonorientable embeddings of the graph , for where and .