Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

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.     

Packing chromatic number of cubic graphs

A packing$k$-coloring of a graph $G$ is a partition of $V\left(G\right)$ into sets $V_1,\dots ,V_k$ such that for each $1\le i\le k$ the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, ${\chi }_p\left(G\right)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $g\ge 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$.     

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.     

Generalizing Tutte’s theorem and maximal non-matchable graphs

A graph $G$ has a perfect matching if and only if $0$ is not a root of its matching polynomial $\mu (G,x)$. Thus, Tutte’s famous theorem asserts that $0$ is not a root of $\mu (G,x)$ if and only if $c_{\mathrm{odd}}(G?S)\le \left|S\right|$ for all $S?V\left(G\right)$, where $c_{\mathrm{odd}}\left(G\right)$ denotes the number of odd components of $G$. Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number $\theta$ as a root of $\mu (G,x)$. We also extend maximal non-matchable graphs to maximal $\theta$-non-matchable graphs and determine the structure of such graphs.     

Helly EPT graphs on bounded degree trees: Characterization and recognition

The edge-intersection graph of a family of paths on a host tree is called an $EPT$ graph. When the tree has maximum degree $h$, we say that the graph is $[h,2,2]$. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly $[h,2,2]$. In this paper, we present a family of $EPT$ graphs called gates which are forbidden induced subgraphs for $[h,2,2]$ graphs. Using these we characterize by forbidden induced subgraphs the Helly $[h,2,2]$ graphs. As a byproduct we prove that in getting a Helly $EPT$-representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly $[h,2,2]$ graphs based on their decomposition by maximal clique separators.     

Reconfiguration graphs of shortest paths

For a graph $G$ and$a,b\in V\left(G\right)$, the shortest path reconfiguration graph of $G$ with respect to $a$ and$b$ is denoted by $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths between $a$ and$b$ in $G$. Two vertices in $V\left(S(G,a,b)\right)$ are adjacent, if their corresponding paths in $G$ differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.     

Closed walks and eigenvalues of Abelian Cayley graphs

We show that Abelian Cayley graphs contain many closed walks of even length. This implies that given $k?3$, for each $\mathrm{?}>0$, there exists $C=C(\mathrm{?},k)>0$ such that for each Abelian group G and each symmetric subset S of G with $1?S$, the number of eigenvalues ${\lambda }_i$ of the Cayley graph $X=X(G,S)$ such that ${\lambda }_i?k?\mathrm{?}$ is at least $C?|G|$. This can be regarded as an analogue for Abelian Cayley graphs of a theorem of Serre for regular graphs. To cite this article: S.M. Cioab?, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

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.