Cliques in dense inhomogeneous random graphs

The theory of dense graph limits comes with a natural sampling process which yields an inhomogeneous variant of the Erd?s–Rényi random graph. Here we study the clique number of these random graphs. We establish the concentration of the clique number of for each fixed n , and give examples of graphons for which exhibits wild long‐term behavior. Our main result is an asymptotic formula which gives the almost sure clique number of these random graphs. We obtain a similar result for the bipartite version of the problem. We also make an observation that might be of independent interest: Every graphon avoiding a fixed graph is countably‐partite. © The Authors Random Structures & Algorithms Published byWiley Periodicals, Inc. Random Struct. Alg., 2016 © 2017 The Authors Random Structures & Algorithms Published by Wiley Periodicals, Inc. Random Struct. Alg., 51, 275–314, 2017     

Graph Decomposition and Parity

Motivated by a recent extension of the zero‐one law by Kolaitis and Kopparty, we study the distribution of the number of copies of a fixed disconnected graph in the random graph . We use an idea of graph decompositions to give a sufficient condition for this distribution to tend to uniform modulo q. We determine the asymptotic distribution of all fixed two‐component graphs in for all q, and we give infinite families of many‐component graphs with a uniform asymptotic distribution for all q. We also prove a negative result that no recursive proof of the simplest form exists for a uniform asymptotic distribution for arbitrary graphs.     

An Algebraic Formulation of the Graph Reconstruction Conjecture

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 .     

Circular coloring of signed graphs

Let ( be two positive integers. We generalize the well‐studied notions of ‐colorings and of the circular chromatic number to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number χ. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on n vertices, if the difference is smaller than 1, then there exists , such that the difference is at most . We also show that the notion of ‐colorings is equivalent to r‐colorings (see [12] (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26 , Springer Berlin Heidelberg, 2006, pp. 497–550)).     

Some results on cyclic interval edge colorings of graphs

A proper edge coloring of a graph G with colors is called a cyclic interval t‐coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree admits a cyclic interval ‐coloring if for every vertex v the degree satisfies either or . We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for ‐biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)‐biregular graphs as well as all ‐biregular () graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.     

On the Decay of Crossing Numbers of Sparse Graphs

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.     

Hadwiger's Conjecture for ℓ‐Link Graphs

In this article, we define and study a new family of graphs that generalizes the notions of line graphs and path graphs. Let G be a graph with no loops but possibly with parallel edges. An ?‐link of G is a walk of G of length in which consecutive edges are different. The ?‐link graph of G is the graph with vertices the ?‐links of G , such that two vertices are joined by edges in if they correspond to two subsequences of each of μ ‐links of G . By revealing a recursive structure, we bound from above the chromatic number of ?‐link graphs. As a corollary, for a given graph G and large enough ?, is 3‐colorable. By investigating the shunting of ?‐links in G , we show that the Hadwiger number of a nonempty is greater or equal to that of G . Hadwiger's conjecture states that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (Eur J Combin 25(6) (2004), 873–876) for line graphs, and hence 1‐link graphs. We prove the conjecture for a wide class of ?‐link graphs.     

On Hypohamiltonian and Almost Hypohamiltonian Graphs

A graph G is almost hypohamiltonian if G is non‐hamiltonian, there exists a vertex w such that is non‐hamiltonian, and for any vertex the graph is hamiltonian. We prove the existence of an almost hypohamiltonian graph with 17 vertices and of a planar such graph with 39 vertices. Moreover, we find a 4‐connected almost hypohamiltonian graph, while Thomassen's question whether 4‐connected hypohamiltonian graphs exist remains open. We construct planar almost hypohamiltonian graphs of order n for every . During our investigation we draw connections between hypotraceable, hypohamiltonian, and almost hypohamiltonian graphs, and discuss a natural extension of almost hypohamiltonicity. Finally, we give a short argument disproving a conjecture of Chvátal (originally disproved by Thomassen), strengthen a result of Araya and Wiener on cubic planar hypohamiltonian graphs, and mention open problems.     

Finite 2‐Geodesic Transitive Graphs of Prime Valency

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.     

Identifying Codes in Line Graphs

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We study the edge‐identifying code problem, i.e. the identifying code problem in line graphs. If denotes the size of a minimum identifying code of an identifiable graph G, we show that the usual bound , where n denotes the order of G, can be improved to in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound , where is the line graph of G, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud, and the first author holds for a subclass of line graphs. Finally, we show that the edge‐identifying code problem is NP‐complete, even for the class of planar bipartite graphs of maximum degree 3 and arbitrarily large girth.     

Graphs with No Induced Five‐Vertex Path or Antipath

We prove that a graph G contains no induced ‐vertex path and no induced complement of a ‐vertex path if and only if G is obtained from 5‐cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class‐preserving operation introduced here.     

On the Caccetta–Häggkvist Conjecture with Forbidden Subgraphs

The Caccetta–Häggkvist conjecture developed in 1978 asserts that every oriented graph on n vertices without oriented cycles of length must contain a vertex of outdegree at most . It has a rather elaborate set of (conjectured) extremal configurations. In this paper, we consider the case that received quite a significant attention in the literature. We identify three oriented graphs on four vertices each that are missing as an induced subgraph in all known extremal examples and prove the Caccetta–Häggkvist conjecture for oriented graphs missing as induced subgraphs any of these oriented graphs, along with . Using a standard method, we can also lift the restriction of being induced, though this makes graphs in our list slightly more complicated.     

Bipartite Intrinsically Knotted Graphs with 22 Edges

A graph is intrinsically knotted if every embedding contains a nontrivially knotted cycle. It is known that intrinsically knotted graphs have at least 21 edges and that the KS graphs, K₇ and the 13 graphs obtained from K₇ by moves, are the only minor minimal intrinsically knotted graphs with 21 edges [1, 9, 11, 12]. This set includes exactly one bipartite graph, the Heawood graph. In this article we classify the intrinsically knotted bipartite graphs with at most 22 edges. Previously known examples of intrinsically knotted graphs of size 22 were those with KS graph minor and the 168 graphs in the K_{3, 3, 1, 1} and families. Among these, the only bipartite example with no Heawood subgraph is Cousin 110 of the family. We show that, in fact, this is a complete listing. That is, there are exactly two graphs of size at most 22 that are minor minimal bipartite intrinsically knotted: the Heawood graph and Cousin 110.     

On (4, 2)‐Choosable Graphs

A graph G is called ‐choosable if for any list assignment L that assigns to each vertex v a set of a permissible colors, there is a b‐tuple L‐coloring of G . An (a , 1)‐choosable graph is also called a‐choosable. In the pioneering article on list coloring of graphs by Erd?s et al.  2 , 2‐choosable graphs are characterized. Confirming a special case of a conjecture in  2 , Tuza and Voigt  3 proved that 2‐choosable graphs are ‐choosable for any positive integer m . On the other hand, Voigt 6 proved that if m is an odd integer, then these are the only ‐choosable graphs; however, when m is even, there are ‐choosable graphs that are not 2‐choosable. A graph is called 3‐choosable‐critical if it is not 2‐choosable, but all its proper subgraphs are 2‐choosable. Voigt conjectured that for every positive integer m , all bipartite 3‐choosable‐critical graphs are ‐choosable. In this article, we determine which 3‐choosable‐critical graphs are (4, 2)‐choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer k such that for any positive integer m , every bipartite 3‐choosable‐critical graph is ‐choosable. Moving beyond 3‐choosable‐critical graphs, we present an infinite family of non‐3‐choosable‐critical graphs that have been shown by computer analysis to be (4, 2)‐choosable. This shows that the family of all (4, 2)‐choosable graphs has rich structure.     

Edge Weighting Functions on Dominating Sets

In this article, we use edge weighting functions on dominating sets to show that if we impose a regularity condition on a graph, then upper bounds on both the upper domination number and the upper total domination number can be greatly improved. More precisely, we prove that for if G is a k‐regular graph on n vertices, then the upper domination number of G is at most , and the upper total domination number of G is at most . Furthermore, we show that these bounds are sharp and characterize the infinite families of graphs that achieve equality in both these bounds.     

Unitary Graphs

Unitary graphs are arc‐transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc‐transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc‐transitive graph of degree and diameter two.     

On Meyniel's conjecture of the cop number

Meyniel conjectured that the cop number c(G) of any connected graph G on n vertices is at most for some constant C. In this article, we prove Meyniel's conjecture in special cases that G has diameter 2 or G is a bipartite graph of diameter 3. For general connected graphs, we prove , improving the best previously known upper‐bound O(n/ lnn) due to Chiniforooshan.     

Edge‐colorings avoiding rainbow stars

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.     

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.