The NLC-width and clique-width for powers of graphs of bounded tree-width

The $k$-power graph of a graph $G$ is a graph with the same vertex set as $G$, in that two vertices are adjacent if and only if, there is a path between them in $G$ of length at most $k$. A $k$-tree-power graph is the $k$-power graph of a tree, a $k$-leaf-power graph is the subgraph of some $k$-tree-power graph induced by the leaves of the tree.We show that (1) every $k$-tree-power graph has NLC-width at most $k+2$ and clique-width at most $k+2+max\{?\frac{k}{2}??1,0\}$, (2) every $k$-leaf-power graph has NLC-width at most $k$ and clique-width at most $k+max\{?\frac{k}{2}??2,0\}$, and (3) every $k$-power graph of a graph of tree-width $l$ has NLC-width at most ${(k+1)}^{l+1}?1$, and clique-width at most $2?{(k+1)}^{l+1}?2$.     

Covering complete partite hypergraphs by monochromatic components

A well-known special case of a conjecture attributed to Ryser (actually appeared in the thesis of Henderson (1971)) states that $k$-partite intersecting hypergraphs have transversals of at most $k?1$ vertices. An equivalent form of the conjecture in terms of coloring of complete graphs is formulated in Gyárfás (1977): if the edges of a complete graph $K$ are colored with $k$ colors then the vertex set of $K$ can be covered by at most $k?1$ sets, each forming a connected graph in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: it was proved in Király (2013) that in every $k$-coloring of the edges of the $r$-uniform complete hypergraph $K^r$ ($r\ge 3$), the vertex set of $K^r$ can be covered by at most $?k∕r?$ sets, each forming a connected hypergraph in some color.Here we investigate the analogue problem for complete $r$-uniform $r$-partite hypergraphs. An edge coloring of a hypergraph is called spanning if every vertex is incident to edges of every color used in the coloring. We propose the following analogue of Ryser’s conjecture.In every spanning $(r+t)$-coloring of the edges of a complete $r$-uniform $r$-partite hypergraph, the vertex set can be covered by at most $t+1$ sets, each forming a connected hypergraph in some color.We show that the conjecture (if true) is best possible. Our main result is that the conjecture is true for $1\le t\le r?1$. We also prove a slightly weaker result for $t\ge r$, namely that $t+2$ sets, each forming a connected hypergraph in some color, are enough to cover the vertex set.To build a bridge between complete $r$-uniform and complete $r$-uniform $r$-partite hypergraphs, we introduce a new notion. A hypergraph is complete $r$-uniform $(r,?)$-partite if it has all $r$-sets that intersect each partite class in at most $?$ vertices (where $1\le ?\le r$).Extending our results achieved for $?=1$, we prove that for any $r\ge 3,2\le ?\le r,k\ge 1+r??$, in every spanning $k$-coloring of the edges of a complete $r$-uniform $(r,?)$-partite hypergraph, the vertex set can be covered by at most $1+?\frac{k?r+??1}{?}?$ sets, each forming a connected hypergraph in some color.     

Locating a robber with multiple probes

We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager (2012). Carragher, Choi, Delcourt, Erickson and West showed that for any $n$-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1∕m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m\ge n$ (Carragher et al., 2012). The present authors showed that, for all but a few small values of $n$, this bound may be improved to $m\ge n∕2$, which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph with the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $\Delta$, which is best possible up to a factor of $(1?o\left(1\right))$.     

A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)

The vertices of Kneser graph $K(n,k)$ are the subsets of $\{1,2,\dots ,n\}$ of cardinality $k$, two vertices are adjacent if and only if they are disjoint. The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ with two vertices adjacent if their distance in $G$ is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when $n=2k+1$. It is believed that $\chi \left(K^2(2k+1,k)\right)=2k+c$ where $c$ is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: $8k∕3+20∕3$ for 1$k\ge 3$ (Kim and Park, 2014) and $32k∕15+32$ for $k\ge 7$ (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to $\chi \left(K^2(2k+1,k)\right)\le 5k∕2+c$, where $c$ is a constant in $\{5∕2,9∕2,5,6\}$, depending on $k\ge 2$.     

Equitable defective coloring of sparse planar graphs

A graph has an equitable, defective $k$-coloring (an ED-$k$-coloring) if there is a $k$-coloring of $V\left(G\right)$ that is defective (every vertex shares the same color with at most one neighbor) and equitable (the sizes of all color classes differ by at most one). A graph may have an ED-$k$-coloring, but no ED-$(k+1)$-coloring. In this paper, we prove that planar graphs with minimum degree at least $2$ and girth at least $10$ are ED-$k$-colorable for any integer $k\ge 3$. The proof uses the method of discharging. We are able to simplify the normally lengthy task of enumerating forbidden substructures by using Hall’s Theorem, an unusual approach.     

Max-cut and extendability of matchings in distance-regular graphs

A connected graph $G$ of even order $v$ is called $t$-extendable if it contains a perfect matching, $t<v/2$ and any matching of $t$ edges is contained in some perfect matching. The extendability of $G$ is the maximum $t$ such that $G$ is $t$-extendable. Since its introduction by Plummer in the 1980s, this combinatorial parameter has been studied for many classes of interesting graphs. In 2005, Brouwer and Haemers proved that every distance-regular graph of even order is $1$-extendable and in 2014, Cioabă and Li showed that any connected strongly regular graph of even order is 3-extendable except for a small number of exceptions.In this paper, we extend and generalize these results. We prove that all distance-regular graphs with diameter $D\ge 3$ are 2-extendable and we also obtain several better lower bounds for the extendability of distance-regular graphs of valency $k\ge 3$ that depend on $k$, $\lambda$ and $\mu$, where $\lambda$ is the number of common neighbors of any two adjacent vertices and $\mu$ is the number of common neighbors of any two vertices in distance two. In many situations, we show that the extendability of a distance-regular graph with valency $k$ grows linearly in $k$. We conjecture that the extendability of a distance-regular graph of even order and valency $k$ is at least $\lceil k/2\rceil -1$ and we prove this fact for bipartite distance-regular graphs.In course of this investigation, we obtain some new bounds for the max-cut and the independence number of distance-regular graphs in terms of their size and odd girth and we prove that our inequalities are incomparable with known eigenvalue bounds for these combinatorial parameters.     

Orthogonally Resolvable Matching Designs

An orthogonally resolvable matching design OMD$(n,k)$ is a partition of the edges of the complete graph $K_n$ into matchings of size $k$, called blocks, such that the blocks can be resolved in two different ways. Such a design can be represented as a square array whose cells are either empty or contain a matching of size $k$, where every vertex appears exactly once in each row and column. In this paper we show that an OMD$(n,k)$ exists if and only if $n\equiv 0(mod2k)$ except when $k=1$ and $n=4$ or $6$.     

On (Kq,k) vertex stable graphs with minimum size

A graph $G$ is a $(K_q,k)$ vertex stable graph if it contains a $K_q$ after deleting any subset of $k$ vertices. We give a characterization of $(K_q,k)$ vertex stable graphs with minimum size for $q=3,4,5$.     

Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are (3,1)-colorable

Given a nonnegative integer $d$ and a positive integer $k$, a graph $G$ is said to be $(k,d)$-colorable if the vertices of $G$ can be colored with $k$ colors such that every vertex has at most $d$ neighbors receiving the same color as itself. Let $?$ be the family of planar graphs without $3$-cycles adjacent to cycles of length 3 or 5. This paper proves that everyone in $?$ is $(3,1)$-colorable. This is the best possible in the sense that there are members in $?$ which are not $(3,0)$-colorable.     

On 1-uniqueness and dense critical graphs for tree-depth

The tree-depth of $G$ is the smallest value of $k$ for which a labeling of the vertices of $G$ with elements from $\{1,\dots ,k\}$ exists such that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is $k$-critical if it has tree-depth $k$ and every proper minor of $G$ has smaller tree-depth.Motivated by a conjecture on the maximum degree of $k$-critical graphs, we consider the property of 1-uniqueness, wherein any vertex of a critical graph can be the unique vertex receiving label 1 in an optimal labeling. Contrary to an earlier conjecture, we construct examples of critical graphs that are not 1-unique and show that 1-unique graphs can have arbitrarily many more edges than certain critical spanning subgraphs. We also show that $(n?1)$-critical graphs on $n$ vertices are 1-unique and use 1-uniqueness to show that the Andrásfai graphs are critical with respect to tree-depth.     

On the vertex-arboricity of planar graphs without 7-cycles

The vertex arboricity $va\left(G\right)$ of a graph $G$ is the minimum number of colors the vertices can be labeled so that each color class induces a forest. It was well-known that $va\left(G\right)\le 3$ for every planar graph $G$. In this paper, we prove that $va\left(G\right)\le 2$ if $G$ is a planar graph without 7-cycles. This extends a result in [A. Raspaud, W. Wang, On the vertex-arboricity of planar graphs, European J. Combin. 29 (2008) 1064–1075] that for each $k\in \{3,4,5,6\}$, planar graphs $G$ without $k$-cycles have $va\left(G\right)\le 2$.     

More odd graph theory from another point of view

The Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of $\left[n\right]=\{1,2,\dots ,n\}$ and an edge between any two vertices that are disjoint. If $n=2k+1$, then $K(n,k)$ is called an odd graph. Let $n>4$ and $1<k<\frac{n}{2}$. In the present paper, we show that if the Kneser graph $K(n,k)$ is of even order where $n$ is an odd integer or both of the integers $n,k$ are even, then $K(n,k)$ is a vertex-transitive non Cayley graph. Although, these are special cases of Godsil [7], unlike his proof that uses some very deep group-theoretical facts, ours uses no heavy group-theoretic facts. We obtain our results by using some rather elementary facts of number theory and group theory. We show that ‘almost all’ odd graphs are of even order, and consequently are vertex-transitive non Cayley graphs. Finally, we show that if $k>4$ is an even integer such that $k$ is not of the form $k=2^t$ for some $t>2$, then the line graph of the odd graph $O_{k+1}$ is a vertex-transitive non Cayley graph.     

On the spanning connectivity of the generalized Petersen graphs P(n,3)

In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph $P(n,3)$. We showed that the $P(n,3)$ is 3-spanning connected for odd $n$. Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the $P(n,3)$. In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for $P(n?6,3)$, where a lattice tail is a trail in the lattice model that represents a path in $P(n,3)$.     

On Vertex Partitions and the Colin de Verdière Parameter

We study vertex partitions of graphs according to their Colin de Verdiere parameter μ. By a result of Ding et al. [DOSOO] we know that any graph G with $\mu (G)⩾2$ admits a vertex partition into two graphs with μ at most $\mu (G)-1$. Here we prove that any graph G with $\mu (G)⩾3$ admits a vertex partition into three graphs with μ at most $\mu (G)-2$. This study is extended to other minor-monotone graph parameters like the Hadwiger number.     

A sufficient condition for DP-4-colorability

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-choosable. Furthermore, Jin et al. (2016) showed that for each $k\in \{3,4,5,6\}$, every signed planar graph without $C_k$ is signed 4-choosable. In this paper, we show that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-DP-colorable, which is an extension of the above results.     

A sharp lower bound on Steiner Wiener index for trees with given diameter

Let $G$ be a connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. For a subset $S$ of $V\left(G\right)$, the Steiner distance$d\left(S\right)$ of $S$ is the minimum size of a connected subgraph whose vertex set contains $S$. For an integer $k$ with $2\le k\le n?1$, the Steiner$k$-Wiener index${\text{SW}}_k\left(G\right)$ is ${\sum }_{S?V\left(G\right),\left|S\right|=k}d\left(S\right)$. In this paper, we introduce some transformations for trees that do not increase their Steiner $k$-Wiener index for $2\le k\le n?1$. Using these transformations, we get a sharp lower bound on Steiner $k$-Wiener index for trees with given diameter, and obtain the corresponding extremal graph as well.