Forcing clique immersions through chromatic number

Building on recent work of Dvořák and Yepremyan, we show that every simple graph of minimum degree $7t+7$ contains $K_t$ as an immersion and that every graph with chromatic number at least $3.54t+4$ contains $K_t$ as an immersion. We also show that every graph on $n$ vertices with no independent set of size three contains $K_{2\lfloor n∕5\rfloor }$ as an immersion.     

The minimum forcing number of perfect matchings in the hypercube

Let $M$ be a perfect matching in a graph. A subset $S$ of $M$ is said to be a forcing set of $M$, if $M$ is the only perfect matching in the graph that contains $S$. The minimum size of a forcing set of $M$ is called the forcing number of $M$. Pachter and Kim (1998) conjectured that the forcing number of every perfect matching in the $n$-dimensional hypercube is $2^{n?2}$, for all $n\ge 2$. This was revised by Riddle (2002), who conjectured that it is at least $2^{n?2}$, and proved it for all even $n$. We show that the revised conjecture holds for all $n\ge 2$. The proof is based on simple linear algebra.     

Strengthening the Murty–Simon conjecture on diameter 2 critical graphs

A graph is diameter-2-critical if its diameter is 2 but the removal of any edge increases the diameter. A well-studied conjecture, known as the Murty–Simon conjecture, states that any diameter-2-critical graph of order $n$ has at most $?n^2∕4?$ edges, with equality if and only if $G$ is a balanced complete bipartite graph. Many partial results about this conjecture have been obtained, in particular it is known to hold for all sufficiently large graphs, for all triangle-free graphs, and for all graphs with a dominating edge. In this paper, we discuss ways in which this conjecture can be strengthened. Extending previous conjectures in this direction, we conjecture that, when we exclude the class of complete bipartite graphs and one particular graph, the maximum number of edges of a diameter-2-critical graph is at most $?{(n?1)}^2∕4?+1$. The family of extremal examples is conjectured to consist of certain twin-expansions of the 5-cycle (with the exception of a set of thirteen special small graphs). Our main result is a step towards our conjecture: we show that the Murty–Simon bound is not tight for non-bipartite diameter-2-critical graphs that have a dominating edge, as they have at most $?n^2∕4??2$ edges. Along the way, we give a shorter proof of the Murty–Simon conjecture for this class of graphs, and stronger bounds for more specific cases. We also characterize diameter-2-critical graphs of order $n$ with maximum degree $n?2$: they form an interesting family of graphs with a dominating edge and $2n?4$ edges.     

Regular saturated graphs and sum-free sets

In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular $K_3$-saturated graph with n vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $k\ge 2$, there is a regular $C_{2k+1}$-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.     

Largest regular multigraphs with three distinct eigenvalues

We deal with connected $k$-regular multigraphs of order $n$ that has only three distinct eigenvalues. In this paper, we study the largest possible number of vertices of such a graph for given $k$. For $k=2,3,7$, the Moore graphs are largest. For $k\ne 2,3,7,57$, we show an upper bound $n\le k^2?k+1$, with equality if and only if there exists a finite projective plane of order $k?1$ that admits a polarity.     

Gallai’s path decomposition conjecture for graphs of small maximum degree

Gallai’s path decomposition conjecture states that the edges of any connected graph on $n$ vertices can be decomposed into at most $\frac{n+1}{2}$ paths. We confirm that conjecture for all graphs with maximum degree at most five.     

Edge decompositions and rooted packings of graphs

Let H be a fixed graph. In this paper we consider the problem of edge decomposition of a graph into subgraphs isomorphic to H or $2K_2$ (a 2-edge matching). We give a partial classification of the problems of existence of such decomposition according to the computational complexity. More specifically, for some large class of graphs H we show that this problem is polynomial time solvable and for some other large class of graphs it is NP-complete. These results can be viewed as some edge decomposition analogs of a result by Loebl and Poljak who classified according to the computational complexity the problem of existence of a graph factor with components isomorphic to H or $K_2$. In the proofs of our results we apply so-called rooted packings into graphs which are mutual generalizations of both edge decompositions and factors of graphs.     

Improved square coloring of planar graphs

Square coloring is a variant of graph coloring where vertices within distance two must receive different colors. When considering planar graphs, the most famous conjecture (Wegner, 1977) states that $\frac{3}{2}\mathrm{\Delta }+1$ colors are sufficient to square color every planar graph of maximum degree Δ. This conjecture has been proven asymptotically for graphs with large maximum degree. We consider here planar graphs with small maximum degree and show that $2\mathrm{\Delta }+7$ colors are sufficient, which improves the best known bounds when $6?\mathrm{\Delta }?31$.     

γ-variable first-order logic of uniform attachment random graphs

We study logical limit laws for uniform attachment random graphs. In this random graph model, vertices and edges are introduced recursively: at time $n+1$, the vertex $n+1$ is introduced together with m edges joining the new vertex with m different vertices chosen uniformly at random from $1,\dots ,n$. We prove that this random graph obeys convergence law for first-order sentences with at most $m?2$ variables.     

A constructive characterization of contraction critical 8-connected graphs with minimum degree 9

An edge of a $k$-connected graph is said to be $k$-contractible if its contraction results in a $k$-connected graph. A $k$-connected graph without $k$-contractible edge is said to be contraction critically $k$-connected. Y. Egawa and W. Mader, independently, showed that the minimum degree of a contraction critical $k$-connected graph is at most $\frac{5k}{4}?1$. Hence, the minimum degree of a contraction critical 8-connected graph is either 8 or 9. This paper shows that a graph $G$ is a contraction critical 8-connected graph with minimum degree 9 if and only if $G$ is the strong product of a contraction critical 4-connected graph $H$ and $K_2$.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

An application of the Gyárfás path argument

We adapt the Gyárfás path argument to prove that $t?2$ cops can capture a robber, in at most $t?1$ moves, in the game of Cops and Robbers played in a graph that does not contain the $t$-vertex path as an induced subgraph.     

Hamiltonian cycles in 7-tough (P3 ∪ 2P1)-free graphs

The toughness of a noncomplete graph G is the maximum real number t such that the ratio of $|S|$ to the number of components of $G?S$ is at least t for every cutset S of G. Determining the toughness for a given graph is NP-hard. Chvátal's toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3\cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3\cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chvátal's toughness conjecture for $(P_3\cup 2P_1)$-free graphs by showing that every 7-tough $(P_3\cup 2P_1)$-free graph on at least three vertices is hamiltonian.     

Group divisible designs with block size 4 where the group sizes are congruent to 2 mod 3

In this paper, we construct a number of 4-GDDs where the group sizes are all congruent to 2 (mod 3). We also show that 4-GDDs of type $2^t{8}^s$ exist for all but a finite number of feasible values of s and t. The largest unknown case has type $2^4{8}^{18}$ and has 152 points. A number of 4-GDDs with at most 50 points are also constructed. These include one of type $4^8{1}^1{10}^1$, the last feasible type of the form $4^s{1}^t{n}^1$ with at most 50 points for which no 4-GDD was known.     

Edge partitions of optimal 2-plane and 3-plane graphs

A topological graph is a graph drawn in the plane. A topological graph is $k$-plane, $k>0$, if each edge is crossed at most $k$ times. We study the problem of partitioning the edges of a $k$-plane graph such that each partite set forms a graph with a simpler structure. While this problem has been studied for $k=1$, we focus on optimal 2-plane and on optimal 3-plane graphs, which are 2-plane and 3-plane graphs with maximum density. We prove the following results. (i) It is not possible to partition the edges of a simple (i.e., with neither self-loops nor parallel edges) optimal 2-plane graph into a 1-plane graph and a forest, while (ii) an edge partition formed by a 1-plane graph and two plane forests always exists and can be computed in linear time. (iii) There exist efficient algorithms to partition the edges of a simple optimal 2-plane graph into a 1-plane graph and a plane graph with maximum vertex degree at most 12, or with maximum vertex degree at most 8 if the optimal2-plane graph is such that its crossing-free edges form a graph with no separating triangles. (iv) There exists an infinite family of simple optimal 2-plane graphs such that in any edge partition composed of a 1-plane graph and a plane graph, the plane graph has maximum vertex degree at least 6 and the 1-plane graph has maximum vertex degree at least 12. (v) Every optimal 3-plane graph whose crossing-free edges form a biconnected graph can be decomposed, in linear time, into a 2-plane graph and two plane forests.