Chromatic number is Ramsey distinguishing

A graph $G$ is Ramsey for a graph $H$ if every colouring of the edges of $G$ in two colours contains a monochromatic copy of $H$. Two graphs $H_1$ and $H_2$ are Ramsey equivalent if any graph $G$ is Ramsey for $H_1$ if and only if it is Ramsey for $H_2$. A graph parameter $s$ is Ramsey distinguishing if $s(H_1)\ne s(H_2)$ implies that $H_1$ and $H_2$ are not Ramsey equivalent. In this paper we show that the chromatic number is a Ramsey distinguishing parameter. We also extend this to the multicolour case and use a similar idea to find another graph parameter which is Ramsey distinguishing.     

The extremal function for K9= minors

We prove the extremal function for $K_9^{=}$ minors, where $K_9^{=}$ denotes the complete graph $K_9$ with two edges removed. In particular, we show that any graph with $n\ge 8$ vertices and at least $6n-20$ edges either contains a $K_9^{=}$ minor or is isomorphic to a graph obtained from disjoint copies of $K_8$ and $K_{2,2,2,2,2}$ by identifying cliques of size 5. We utilize computer assistance to prove one of our lemmas.     

Orientations of graphs avoiding given lists on out-degrees

Let $G$ be a graph and $F:V\left(G\right)\to 2^{\mathbb{N}}$ be a mapping. The graph $G$ is said to be $F$- avoiding if there exists an orientation $O$ of $G$ such that $d_O^{+}\left(v\right)\notin F\left(v\right)$ for every $v\in V\left(G\right)$, where $d_O^{+}\left(v\right)$ denotes the out-degree of $v$ in the directed graph $G$ with respect to $O$. In this paper it is shown that if $G$ is bipartite and $\mid F\left(v\right)\mid \le d_G\left(v\right)/2$ for every $v\in V\left(G\right)$, then $G$ is $F$-avoiding. The bound $\mid F\left(v\right)\mid \le d_G\left(v\right)/2$ is best possible. For every graph $G$, we conjecture that if $\mid F\left(v\right)\mid \le \frac{1}{2}\left(d_G\left(v\right)-1\right)$ for every $v\in V\left(G\right)$, then $G$ is $F$-avoiding. We also argue about this conjecture for the best possibility of the conditions and also show some partial solutions.     

On induced subgraphs of the Hamming graph

In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph $G$ with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of $G$ with $\alpha \left(G\right)+1$ vertices, where $\alpha \left(G\right)$ denotes the size of the largest independent set in $G$? We study this question for $H\left(n,k\right)$, the $n$‐dimensional Hamming graph over an alphabet of size $k$. Generalizing a construction by Chung et al. (JCT‐A, 1988), we prove that $H\left(n,k\right)$ has an induced subgraph with more than $\alpha \left(H\left(n,k\right)\right)$ vertices and maximum degree at most $?\sqrt{n}?$. Chung et al. proved this statement for $k=2$ (the $n$‐dimensional cube).     

Independent set and matching permutations

Let $G$ be a graph $G$ whose largest independent set has size $m$. A permutation $\pi$ of $\left\{1,\text{…},m\right\}$ is an independent set permutation of $G$ if $$a_{\pi \left(1\right)}\left(G\right)\le a_{\pi \left(2\right)}\left(G\right)\le \mathrm{?}\le a_{\pi \left(m\right)}\left(G\right),$$ where $a_k\left(G\right)$ is the number of independent sets of size $k$ in $G$. In 1987 Alavi, Malde, Schwenk, and Erd?s proved that every permutation of $\left\{1,\text{…},m\right\}$ is an independent set permutation of some graph with $\alpha \left(G\right)=m$, that is, with the largest independent set having size $m$. They raised the question of determining, for each $m$, the smallest number $f\left(m\right)$ such that every permutation of $\left\{1,\text{…},m\right\}$ is an independent set permutation of some graph with $\alpha \left(G\right)=m$ and with at most $f\left(m\right)$ vertices, and they gave an upper bound on $f\left(m\right)$ of roughly $m^{2m}$. Here we settle the question, determining $f\left(m\right)=m^m$, and make progress on a related question, that of determining the smallest order such that every permutation of $\left\{1,\text{…},m\right\}$ is the unique independent set permutation of some graph of at most that order. More generally we consider an extension of independent set permutations to weak orders, and extend Alavi et al.'s main result to show that every weak order on $\left\{1,\text{…},m\right\}$ can be realized by the independent set sequence of some graph with $\alpha \left(G\right)=m$ and with at most $m^{m+2}$ vertices. Alavi et al. also considered matching permutations, defined analogously to independent set permutations. They observed that not every permutation of $\left\{1,\text{…},m\right\}$ is a matching permutation of some graph with the largest matching having size $m$, putting an upper bound of $2^{m?1}$ on the number of matching permutations of $\left\{1,\text{…},m\right\}$. Confirming their speculation that this upper bound is not tight, we improve it to $O\left(2^m∕\sqrt{m}\right)$.     

Highly edge-connected regular graphs without large factorizable subgraphs

We construct highly edge-connected $r$-regular graphs of even order which do not contain $r?2$ pairwise disjoint perfect matchings. When $r$ is a multiple of 4, the result solves a problem of Thomassen [4].     

Sparse halves in K 4-free graphs

A conjecture of Chung and Graham states that every $K_4$-free graph on $n$ vertices contains a vertex set of size $?n∕2?$ that spans at most $n^2∕18$ edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.     

Finding any given 2‐factor in sparse pseudorandom graphs efficiently

Given an $n$‐vertex pseudorandom graph $G$ and an $n$‐vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, that is, an embedding $\phi :V\left(H\right)\to V\left(G\right)$ so that $\phi \left(u\right)\phi \left(v\right)\in E\left(G\right)$ for all $uv\in E\left(H\right)$. Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $\left(p,\lambda \right)$‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, $\mathrm{\Omega }\left(pn\right)$. A $\left(p,\lambda \right)$‐bijumbled graph is characterised through the discrepancy property: $|e\left(A,B\right)?p|A||B||<\lambda \sqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n/\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.     

Triangles in C 5-free graphs and hypergraphs of girth six

We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$\left(1+o\left(1\right)\right)\frac{1}{3\sqrt{2}}{n}^{3∕2}.$$ We show a connection to $r$-uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced-$C_4$-free and $C_5$-free graph.     

Degree sum conditions for the existence of homeomorphically irreducible spanning trees

In 1990, Albertson, Berman, Hutchinson, and Thomassen proved a theorem which gives a minimum degree condition for the existence of a spanning tree with no vertices of degree 2. Such a spanning tree is called a homeomorphically irreducible spanning tree (HIST). In this paper, we prove that every graph of order $n$ ($n\ge 8$) contains a HIST if $d(u)+d(v)\ge n?1$ for any nonadjacent vertices $u$ and $v$. The degree sum condition is best possible.     

Partitions of hypergraphs under variable degeneracy constraints

The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph $H$ and a sequence $f=\left(f_1,f_2,\text{…},f_p\right)$ of $p\ge 1$ vertex functions $f_i:V\left(H\right)\to {\mathbb{N}}_0$ such that $f_1\left(v\right)+f_2\left(v\right)+\mathrm{?}+f_p\left(v\right)\ge d_H\left(v\right)$ for all $v\in V\left(H\right)$, we want to find a sequence $\left(H_1,H_2,\text{…},H_p\right)$ of vertex disjoint induced subhypergraphs containing all vertices of $H$ such that each hypergraph $H_i$ is strictly $f_i$‐degenerate, that is, for every nonempty subhypergraph $H\prime ?H_i$ there is a vertex $v\in V\left(H\prime \right)$ such that $d_{H\prime }\left(v\right)<f_i\left(v\right)$. Our main result in this paper says that such a sequence of hypergraphs exists if and only if $\left(H,f\right)$ is not a so‐called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. Our main result has several interesting applications related to generalized hypergraph coloring problems.     

Bounding the mim-width of hereditary graph classes

A large number of $\mathsf{NP}$-hard graph problems are solvable in $\mathsf{XP}$ time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider maximum-induced matching width (mim-width), a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is “quickly computable” for the graph class under consideration. We start by extending the toolkit for proving (un)boundedness of mim-width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes, and make a comparison with clique-width, a more restrictive width parameter that has been well studied. We prove that for a given graph $H$, the class of $H$-free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for $(H_1,H_2)$-free graphs. We identify several general classes of $(H_1,H_2)$-free graphs having unbounded clique-width, but bounded mim-width; moreover, we show that a branch decomposition of constant mim-width can be found in polynomial time for these classes. Hence, these results have algorithmic implications: when the input is restricted to such a class of $(H_1,H_2)$-free graphs, many problems become polynomial-time solvable, including classical problems, such as $k$- Colouring and Independent Set , domination-type problems known as Locally Checkable Vertex Subset and Vertex Partitioning (LC-VSVP) problems, and distance versions of LC-VSVP problems, to name just a few. We also prove a number of new results showing that, for certain $H_1$ and $H_2$, the class of $(H_1,H_2)$-free graphs has unbounded mim-width. Boundedness of clique-width implies boundedness of mim-width. By combining our results with the known bounded cases for clique-width, we present summary theorems of the current state of the art for the boundedness of mim-width for $(H_1,H_2)$-free graphs. In particular, we classify the mim-width of $(H_1,H_2)$-free graphs for all pairs $(H_1,H_2)$ with $\mid V(H_1)\mid +\mid V(H_2)\mid \le 8$. When $H_1$ and $H_2$ are connected graphs, we classify all pairs $(H_1,H_2)$ except for one remaining infinite family and a few isolated cases.     

Order plus size of τ‐critical graphs

Let $G=\left(V,E\right)$ be a $\tau$‐critical graph with $\tau \left(G\right)=t$. Erd?s and Gallai proved that $\mid V\mid \le 2t$ and the bound $\mid E\mid \le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)$ was obtained by Erd?s, Hajnal, and Moon. We give here the sharp combined bound $\mid E\mid +\mid V\mid \le \left(\genfrac{}{}{0ex}{}{t+2}{2}\right)$ and find all graphs with equality.     

Proper‐walk connection number of graphs

This paper studies the problem of proper‐walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph, that is, a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$.     

On the maximum number of copies of H in graphs with given size and order

We study the maximum number $ex\left(n,e,H\right)$ of copies of a graph $H$ in graphs with a given number of vertices and edges. We show that for any fixed graph $H,ex\left(n,e,H\right)$ is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.     

Even cycle creating paths

We say that two graphs $H_1,H_2$ on the same vertex set are $G$-creating if the union of the two graphs contains $G$ as a subgraph. Let $H\left(n,k\right)$ be the maximum number of pairwise $C_k$-creating Hamiltonian paths of the complete graph $K_n$. The behavior of $H\left(n,2k+1\right)$ is much better understood than the behavior of $H\left(n,2k\right)$, the former is an exponential function of $n$ whereas the latter is larger than exponential, for every fixed $k$. We study $H\left(n,k\right)$ for fixed $k$ and $n$ tending to infinity. The only nontrivial upper bound on $H\left(n,2k\right)$ was proved by Cohen, Fachini, and Körner in the case of $k=2$: $$n^{(1/2)n-o\left(n\right)}\le H\left(n,4\right)\le n^{\left(1-1/4\right)n-o\left(n\right)}\mathrm{.}$$ In this paper, we generalize their method to prove that for every $k\ge 2$, $$n^{(1/k)n-o\left(n\right)}\le H\left(n,2k\right)\le n^{\left(1-2/(3k^2-2k)\right)n-o\left(n\right)}$$ and a similar, slightly better upper bound holds when $k$ is odd. Our proof uses constructions of bipartite, regular, $C_{2k}$-free graphs with many edges given in papers by Reiman, Benson, Lazebnik, Ustimenko, and Woldar.     

Colourings of star systems

An $e$‐star is a complete bipartite graph $K_{1,e}$. An $e$‐star system of order $n>1,S_e\left(n\right)$, is a partition of the edges of the complete graph $K_n$ into $e$‐stars. An $e$‐star system is said to be $k$‐colourable if its vertex set can be partitioned into $k$ sets (called colour classes) such that no $e$‐star is monochromatic. The system $S_e\left(n\right)$ is $k$‐chromatic if $S_e\left(n\right)$ is $k$‐colourable but is not $\left(k?1\right)$‐colourable. If every $k$‐colouring of an $e$‐star system can be obtained from some $k$‐colouring $?$ by a permutation of the colours, we say that the system is uniquely $k$‐colourable. In this paper, we first show that for any integer $k?2$, there exists a $k$‐chromatic 3‐star system of order $n$ for all sufficiently large admissible $n$. Next, we generalize this result for $e$‐star systems for any $e?3$. We show that for all $k?2$ and $e?3$, there exists a $k$‐chromatic $e$‐star system of order $n$ for all sufficiently large $n$ such that $n\equiv 0,1$ (mod $2e$). Finally, we prove that for all $k?2$ and $e?3$, there exists a uniquely $k$‐chromatic $e$‐star system of order $n$ for all sufficiently large $n$ such that $n\equiv 0,1$ (mod $2e$).     

Short k‐radius sequences, k‐difference sequences and universal cycles

An $n$‐ary $k$‐radius sequence is a finite sequence of elements taken from an alphabet of size $n$ in which any two distinct elements occur within distance $k$ of each other somewhere in the sequence. The study of constructing short $k$‐radius sequences was motivated by some problems occurring in large data transfer. Let $f_k\left(n\right)$ be the shortest length of any $n$‐ary $k$‐radius sequence. We show that the conjecture $f_k\left(n\right)=\frac{n^2}{2k}+O\left(n\right)$ by Bondy et al is true for $k\le 4$, and determine the exact values of $f_2\left(n\right)$ for new infinitely many $n$. Further, we investigate new sequences which we call $k$‐difference, as they are related to $k$‐radius sequences and seem to be interesting in themselves. Finally, we answer a question about the optimal length of packing and covering analogs of universal cycles proposed by D?bski et al.