Histories in Path Graphs

For a given graph G and a positive integer r the r-path graph, $P_r(G)$, has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length $r-1$, and their union forms either a cycle or a path of length $r+1$ in G. Let $P_r^k(G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_r^k(G)$. The k-history $P_r^{-k}(H)$ is a subgraph of G that is induced by all edges that take part in the recursive definition of H. We present some general properties of k-histories and give a complete characterization of graphs that are k-histories of vertices of 2-path graph operator.     

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.     

Some Ramsey–Turán type problems and related questions

In this paper the following Ramsey–Turán type problem is one of several addressed. For which graphs $G$ does there exist a constant $0<c<1$ such that when $H$ is a graph of order the Ramsey number $r\left(G\right)$ with $\delta \left(H\right)>c\left|H\right|$, then any 2-edge coloring of $H$ contains a monochromatic copy of $G$? Specific results, conjectures, and questions with suggested values for $c$ are considered when $G$ is an odd cycle, path, or tree of limited maximum degree. Another variant is to 2-edge color a replacement for the graph $K_{r\left(G\right)}$ by a balanced multipartite graph of approximately the same order with the same consequence, a monochromatic $G$.     

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

Vertex partitions of non-complete graphs into connected monochromatic k-regular graphs

In a landmark paper, Erd?s et al. (1991) [3] proved that if $G$ is a complete graph whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most $c{r}^{2}logr$ monochromatic, vertex disjoint cycles for some constant $c$. Sárközy extended this result to non-complete graphs, and Sárközy and Selkow extended it to $k$-regular subgraphs. Generalizing these two results, we show that if $G$ is a graph with independence number $\alpha \left(G\right)=\alpha$ whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most ${\left(\alpha r\right)}^{c(\alpha rlog\left(\alpha r\right)+k)}$ vertex disjoint connected monochromatic$k$-regular subgraphs of $G$ for some constant $c$.     

List r-hued chromatic number of graphs with bounded maximum average degrees

For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring $c$ with at most $k$ colors such that for any vertex $v$ with degree $d\left(v\right)$, there are at least min$\{d\left(v\right),r\}$ different colors present at the neighborhood of $v$. The $r$-hued chromatic number of $G$, ${\chi }_r\left(G\right)$, is the least integer $k$ such that a $(k,r)$-coloring of $G$ exists. The list$r$-hued chromatic number${\chi }_{L,r}\left(G\right)$ of $G$ is similarly defined. Thus if $\Delta \left(G\right)\ge r$, then ${\chi }_{L,r}\left(G\right)\ge {\chi }_r\left(G\right)\ge r+1$. We present examples to show that, for any sufficiently large integer $r$, there exist graphs with maximum average degree less than 3 that cannot be $(r+1,r)$-colored. We prove that, for any fraction $q<\frac{14}{5}$, there exists an integer $R=R\left(q\right)$ such that for each $r\ge R$, every graph $G$ with maximum average degree $q$ is list $(r+1,r)$-colorable. We present examples to show that for some $r$ there exist graphs with maximum average degree less than 4 that cannot be $r$-hued colored with less than $\frac{3r}{2}$ colors. We prove that, for any sufficiently small real number $?>0$, there exists an integer $h=h\left(?\right)$ such that every graph $G$ with maximum average degree $4??$ satisfies ${\chi }_{L,r}\left(G\right)\le r+h\left(?\right)$. These results extend former results in Bonamy et al. (2014).     

Graph coloring and Graham’s greatest common divisor problem

In this paper we introduce and study two graph coloring problems and relate them to some deep number-theoretic problems. For a fixed positive integer $k$ consider a graph $B_k$ whose vertex set is the set of all positive integers with two vertices $a,b$ joined by an edge whenever the two numbers $a∕gcd(a,b)$ and $b∕gcd(a,b)$ are both at most $k$. We conjecture that the chromatic number of every such graph $B_k$ is equal to $k$. This would generalize the greatest common divisor problem of Graham from 1970; in graph-theoretic terminology it states that the clique number of $B_k$ is equal to $k$. Our conjecture is connected to integer lattice tilings and partial Latin squares completions.     

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 girth and diameter of generalized Johnson graphs

Let $v>k>i$ be non-negative integers. The generalized Johnson graph, $J(v,k,i)$, is the graph whose vertices are the $k$-subsets of a $v$-set, where vertices $A$ and $B$ are adjacent whenever $|A\cap B|=i$. In this article, we derive general formulas for the girth and diameter of $J(v,k,i)$. Additionally, we provide a formula for the distance between any two vertices $A$ and $B$ in terms of the cardinality of their intersection.     

3-dynamic coloring of planar triangulations

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that any vertex $v$ has at least $min\{r,{deg}_G\left(v\right)\}$ distinct colors in $N_G\left(v\right)$. The $r$-dynamic chromatic number${\chi }_r^d\left(G\right)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$.Loeb et al. (2018) showed that if $G$ is a planar graph, then ${\chi }_3^d\left(G\right)\le 10$, and there is a planar graph $G$ with ${\chi }_3^d\left(G\right)=7$. Thus, finding an optimal upper bound on ${\chi }_3^d\left(G\right)$ for a planar graph $G$ is a natural interesting problem. In this paper, we show that ${\chi }_3^d\left(G\right)\le 5$ if $G$ is a planar triangulation. The upper bound is sharp.     

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

Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

Coloring circle graphs

Circle graph is an intersection graph of chords of a circle. We denote the class of circle graphs by cir. In this paper we investigate the chromatic number of the circle graph as a function of the size of maximum clique $\omega =\omega (G)$. More precisely we investigate $f(k)=\max \{\chi (G)|G\in \text{CIR }\mathrm{\&}\omega (G)⩽k\}$. Kratochvíl and Kostochka showed that $f(k)⩽50\cdot 2^k-32k-64$. The best lower bound is by Kostochka and is $f(k)=\mathrm{\Omega }(k\log k)$. We improve the upper bound to $f(k)⩽21\cdot 2^k-24k-24$. We also present the bound $\chi (G)⩽\omega \cdot \log n$ which shows, that the circle graphs with small maximum clique and large chromatic number must have many vertices.