Search

We show that for every $\eta>0$, there exists $n_0$ such that for every even $n$, $n\ge n_0$, and every graph $G$ with $(2+\eta)n$ vertices and minimum degree at least $(7/4+4\eta)n$, each colouring of the edges of $G$ with three colours results in a monochromatic cycle of length $n$.

A graph is called equimatchable if all of its maximal matchings have the same size. Frendrup et al. [8] provided a characterization of equimatchable graphs with girth at least $5$. In this paper, we extend this result by providing a complete structural characterization of equimatchable graphs with girth at least $4$, i.e., equimatchable graphs with no triangle, by identifying the equimatchable triangle-free graph families. Our characterization also extends the result given by Akbari et al. in [1], which proves that the only connected triangle-free equimatchable $r$-regular graphs are $C_5$, $C_7$ and $K_{r,r}$, where $r$ is a positive integer. Given a non-bipartite graph, our characterization implies a linear time recognition algorithm for triangle-free equimatchable graphs.

Let $lct(G)$ be the minimum cardinality of a set of vertices that intersects every longest cycle of a 2-connected graph $G$. We show that $lct(G)\leq k-1$ if $G$ is a partial $k$-tree and that $lct(G)\leq \max \{1, {\omega(G){-}3}\}$ if $G$ is chordal, where $\omega(G)$ is the cardinality of a maximum clique in $G$. Those results imply that all longest cycles intersect in 2-connected series parallel graphs and in 3-trees.

A set $S$ of vertices in a graph $G$ is a dominating set if every vertex of $G$ is in $S$ or is adjacent to a vertex in $S$. If, in addition, $S$ is an independent set, then $S$ is an independent dominating set. The domination number $\gamma(G)$ of $G$ is the minimum cardinality of a dominating set in $G$, while the independent domination number $i(G)$ of $G$ is the minimum cardinality of an independent dominating set in $G$. We prove that for all integers $k \geq 3$ it holds that if $G$ is a connected $k$-regular graph, then $\frac{i(G)}{\gamma(G)} \leq \frac{k}{2}$, with equality if and only if $G = K_{k,k}$. The result was previously known only for $k\leq 6$. This affirmatively answers a recent question of Babikir and Henning.

A graph $G$ is said to be $d$-distinguishable if there is a labeling of the vertices with $d$ labels so that only the trivial automorphism preserves the labels. The smallest such $d$ is the distinguishing number, Dist($G$). A subset of vertices $S$ is a determining set for $G$ if every automorphism of $G$ is uniquely determined by its action on $S$. The size of a smallest determining set for $G$ is called the determining number, Det($G$). The orthogonality graph $\Omega_{2k}$ has vertices which are bitstrings of length $2k$ with an edge between two vertices if they differ in precisely $k$ bits. This paper shows that Det($\Omega_{2k}$) $= 2^{2k-1}$ and that if $\binom{m}{2} \geq 2k$ then $2

A linear forest is a forest in which every connected component is a path. The linear arboricity of a graph $G$ is the minimum number of linear forests of $G$ covering all edges. In 1980, Akiyama, Exoo and Harary proposed a conjecture, known as the Linear Arboricity Conjecture (LAC), stating that every $d$-regular graph $G$ has linear arboricity $\lceil \frac{d+1}{2} \rceil$. In 1988, Alon proved that the LAC holds asymptotically. In 1999, the list version of the LAC was raised by An and Wu, which is called the List Linear Arboricity Conjecture. In this article, we prove that the List Linear Arboricity Conjecture holds asymptotically., Comment: 17 pages

The edge clique cover number ecc(G) of a graph G is size of the smallest collection of complete sub-graphs whose union covers all edges of G. Chen, Jacobson, Kezdy, Lehel, Scheinerman, and Wang conjectured in 2000 that if G is claw-free, then ecc(G) is bounded above by its order (denoted n). Recently, Javadi and Hajebi verified this conjecture for claw-free graphs with independence number at least three. We study the edge clique cover number of graphs with independence number two, which are necessarily claw-free. We give the first known proof of a linear bound in n for ecc(G) for such graphs, improving upon the bound of O (n 4/3 log 1/3 n) due to Javadi, Maleki and Omoomi. More precisely we prove that ecc(G) is at most the minimum of n + δ (G) and 2n − Ω (n log n), where δ (G) is the minimum degree of G. In the fractional version of the problem, we improve these upper bounds to 3 2 n. We also verify the conjecture for some specific subfamilies, for example when the edge packing number with respect to cliques (a lower bound for ecc(G)) equals n, and when G contains no induced subgraph isomorphic to H where H is any fixed graph of order 4.

A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.

The canonical double cover $\D(\Gamma)$ of a graph $\Gamma$ is the direct product of $\Gamma$ and $K_2$. If $\Aut(\D(\Gamma))\cong\Aut(\Gamma)\times\ZZ_2$ then $\Gamma$ is called stable; otherwise $\Gamma$ is called unstable. An unstable graph is said to be nontrivially unstable if it is connected, non-bipartite and no two vertices have the same neighborhood. In 2008 Wilson conjectured that, if the generalized Petersen graph $\GP(n,k)$ is nontrivially unstable, then both $n$ and $k$ are even, and either $n/2$ is odd and $k^2\equiv\pm 1 \pmod{n/2}$, or $n=4k$. In this note we prove that this conjecture is true. At the same time we determine all possible isomorphisms among the generalized Petersen graphs, the canonical double covers of the generalized Petersen graphs, and the double generalized Petersen graphs. Based on these we completely determine the full automorphism group of the canonical double cover of $\GP(n,k)$ for any pair of integers $n, k$ with $1 \leqslant k < n/2$., Comment: This is the final version that will appear in Journal of Graph Theory

The well-known 5-flow Conjecture of Tutte, stated originally for integer flows, claims that every bridgeless graph has circular flow number at most 5. It is a classical result that the study of the 5-flow Conjecture can be reduced to cubic graphs, in particular to snarks. However, very few procedures to construct snarks with circular flow number 5 are known. In the first part of this paper, we summarise some of these methods and we propose new ones based on variations of the known constructions. Afterwards, we prove that all such methods are nothing but particular instances of a more general construction that we introduce into detail. In the second part, we consider many instances of this general method and we determine when our method permits to obtain a snark with circular flow number 5. Finally, by a computer search, we determine all snarks having circular flow number 5 up to 36 vertices. It turns out that all such snarks of order at most 34 can be obtained by using our method, and that the same holds for 96 of the 98 snarks of order 36 with circular flow number 5., 27 pages; submitted for publication

For a graph $G$, the mean subtree order of $G$ is the average order of a subtree of $G$. In this note, we provide counterexamples to a recent conjecture of Chin, Gordon, MacPhee, and Vincent, that for every connected graph $G$ and every pair of distinct vertices $u$ and $v$ of $G$, the addition of the edge between $u$ and $v$ increases the mean subtree order. In fact, we show that the addition of a single edge between a pair of nonadjacent vertices in a graph of order $n$ can decrease the mean subtree order by as much as $n/3$ asymptotically. We propose the weaker conjecture that for every connected graph $G$ which is not complete, there exists a pair of nonadjacent vertices $u$ and $v$, such that the addition of the edge between $u$ and $v$ increases the mean subtree order. We prove this conjecture in the special case that $G$ is a tree., Comment: 13 pages

The chromatic polynomial $P(G,x)$ of a graph $G$ of order $n$ can be expressed as $\sum\limits_{i=1}^n(-1)^{n-i}a_{i}x^i$, where $a_i$ is interpreted as the number of broken-cycle free spanning subgraphs of $G$ with exactly $i$ components. The parameter $\epsilon(G)=\sum\limits_{i=1}^n (n-i)a_i/\sum\limits_{i=1}^n a_i$ is the mean size of a broken-cycle-free spanning subgraph of $G$. In this article, we confirm and strengthen a conjecture proposed by Lundow and Markstr\"{o}m in 2006 that $\epsilon(T_n)< \epsilon(G), Comment: 20 pages, 23 references. To appear in J. Graph Theory

Let ${\cal M}$ be a map with the underlying graph $\Gamma$. The automorphism group $Aut({\cal M})$ induces a natural action on the set of all vertex-edge-face incident triples, called {\em flags} of ${\cal M}$. The map ${\cal M}$ is said to be a {\em $k$-orbit} map if $Aut({\cal M})$ has $k$ orbits on the set of all flags of ${\cal M}$. It is known that there are seven different classes of $2$-orbit maps, with only four of them corresponding to arc-transitive maps, that is maps for which $Aut{\cal M}$ acts arc-transitively on the underlying graph $\Gamma$. The Petrie dual operator links these four classes in two pairs, one of which corresponds to the chiral maps and their Petrie duals. In this paper we focus on the other pair of classes of $2$-orbit arc-transitive maps. We investigate the connection of these maps to consistent cycles of the underlying graph with special emphasis on such maps of smallest possible valence, namely $4$. We then give a complete classification of such maps whose underlying graphs are arc-transitive Rose Window graphs.

A clique (resp., independent set) in a graph is strong if it intersects every maximal independent sets (resp., every maximal cliques). A graph is CIS if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique $C$ in a vertex-transitive graph $\Gamma$ is strong if and only if $|C||I|=|V(\Gamma)|$ for every maximal independent set $I$ of $\Gamma$. Based on this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of $5$-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most $5$ that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable.

An orientation of $G$ is a digraph obtained from $G$ by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation \emph{proper} if neighbouring vertices have different in-degrees. The proper orientation number of a graph $G$, denoted by $\vec{\chi}(G)$, is the minimum maximum in-degree of a proper orientation of G. Araujo et al. (Theor. Comput. Sci. 639 (2016) 14--25) asked whether there is a constant $c$ such that $\vec{\chi}(G)\leq c$ for every outerplanar graph $G$ and showed that $\vec{\chi}(G)\leq 7$ for every cactus $G.$ We prove that $\vec{\chi}(G)\leq 3$ if $G$ is a triangle-free $2$-connected outerplanar graph and $\vec{\chi}(G)\leq 4$ if $G$ is a triangle-free bridgeless outerplanar graph.

A compact graph-like space is a triple $(X,V,E)$ where $X$ is a compact, metrizable space, $V \subseteq X$ is a closed zero-dimensional subset, and $E$ is an index set such that $X \setminus V \cong E \times (0,1)$. New characterizations of compact graph-like spaces are given, connecting them to certain classes of continua, and to standard subspaces of Freudenthal compactifications of locally finite graphs. These are applied to characterize Eulerian graph-like compacta.

For a graph $G$, let $\sigma_{2}(G)$ be the minimum degree sum of two non-adjacent vertices in $G$. A chord of a cycle in a graph $G$ is an edge of $G$ joining two non-consecutive vertices of the cycle. In this paper, we prove the following result, which is an extension of a result of Brandt et al. (J. Graph Theory 24 (1997) 165-173) for large graphs: For positive integers $k$ and $c$, there exists an integer $f(k,c)$ such that, if $G$ is a graph of order $n \ge f(k, c)$ and $\sigma_{2}(G) \ge n$, then $G$ can be partitioned into $k$ vertex-disjoint cycles, each of which has at least $c$ chords.

Chen, Faudree, Gould, Jacobson, and Lesniak determined the minimum degree threshold for which a balanced $k$-partite graph has a Hamiltonian cycle. We give an asymptotically tight minimum degree condition for Hamiltonian cycles in arbitrary $k$-partite graphs in which all parts have at most $n/2$ vertices (a necessary condition). To do this, we first prove a general result which both simplifies the process of checking whether a graph $G$ is a robust expander and gives useful structural information in the case when $G$ is not a robust expander. Then we use this result to prove that any $k$-partite graph satisfying the minimum degree condition is either a robust expander or else contains a Hamiltonian cycle directly.

It is well-known that in every $r$-coloring of the edges of the complete bipartite graph $K_{m,n}$ there is a monochromatic connected component with at least ${m+n\over r}$ vertices. In this paper we study an extension of this problem by replacing complete bipartite graphs by bipartite graphs of large minimum degree. We conjecture that in every $r$-coloring of the edges of an $(X,Y)$-bipartite graph with $|X|=m$, $|Y|=n$, $\delta(X,Y) > \left( 1 - \frac{1}{r+1}\right) n$ and $\delta(Y,X) > \left( 1 - \frac{1}{r+1}\right) m$, there exists a monochromatic component on at least $\frac{m+n}{r}$ vertices (as in the complete bipartite graph). If true, the minimum degree condition is sharp (in that both inequalities cannot be made weak when $m$ and $n$ are divisible by $r+1$). We prove the conjecture for $r=2$ and we prove a weaker bound for all $r\geq 3$. As a corollary, we obtain a result about the existence of monochromatic components with at least $\frac{n}{r-1}$ vertices in $r$-colored graphs with large minimum degree.

DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvo\v{r}\'{a}k and Postle. In this paper we introduce and study the fractional DP-chromatic number $\chi_{DP}^\ast(G)$. We characterize all connected graphs $G$ such that $\chi_{DP}^\ast(G) \leq 2$: they are precisely the graphs with no odd cycles and at most one even cycle. By a theorem of Alon, Tuza, and Voigt, the fractional list-chromatic number $\chi_\ell^\ast(G)$ of any graph $G$ equals its fractional chromatic number $\chi^\ast(G)$. This equality does not extend to fractional DP-colorings. Moreover, we show that the difference $\chi^\ast_{DP}(G) - \chi^\ast(G)$ can be arbitrarily large, and, furthermore, $\chi^\ast_{DP}(G) \geq d/(2 \ln d)$ for any graph $G$ of maximum average degree $d \geq 4$. On the other hand, we show that this asymptotic lower bound is tight for a large class of graphs that includes all bipartite graphs as well as many graphs of high girth and high chromatic number.

Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge-connected graph has an edge orientation in which every out-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge connected 5-regular graphs.

Truemper configurations (thetas, pyramids, prisms, and wheels) have played an important role in the study of complex hereditary graph classes (e.g. the class of perfect graphs and the class of even-hole-free graphs), appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this paper, we study the structure of graphs that contain (as induced subgraphs) no Truemper configurations other than (possibly) universal wheels and twin wheels. We also study several subclasses of this class. We use our structural results to analyze the complexity of the recognition, maximum weight clique, maximum weight stable set, and optimal vertex coloring problems for these classes. We also obtain polynomial χ-bounding functions for these classes.

We present a construction of two infinite graphs $G_1$ and $G_2$, and of an infinite set $\mathscr{F}$ of graphs such that $\mathscr{F}$ is an antichain with respect to the immersion relation and, for each graph $G$ in $\mathscr{F}$, both $G_1$ and $G_2$ are subgraphs of $G$, but no graph properly immersed in $G$ admits an immersion of $G_1$ and of $G_2$. This shows that the class of infinite graphs ordered by the immersion relation does not have the finite intertwine property.

We show that any complete $k$-partite graph $G$ on $n$ vertices, with $k \ge 3$, whose edges are two-coloured, can be covered with two vertex-disjoint monochromatic paths of distinct colours. We prove this under the necessary assumption that the largest partition class of $G$ contains at most $n/2$ vertices. This extends known results for complete and complete bipartite graphs. Secondly, we show that in the same situation, all but $o(n)$ vertices of the graph can be covered with two vertex-disjoint monochromatic cycles of distinct colours, if colourings close to a split colouring are excluded. From this we derive that the whole graph, if large enough, may be covered with 14 vertex-disjoint monochromatic cycles.

The famous Kőnig‐Egervary theorem is equivalent to the statement that the matching number equals the vertex cover number for every induced subgraph of some graph if and only if that graph is bipartite. Inspired by this result, we consider the set Gk of all graphs such that, for every induced subgraph, the maximum number of disjoint paths of order k equals the minimum order of a set of vertices intersecting all paths of order k. For k ∈ {3,4}, we give complete structural descriptions of the graphs in Gk. Furthermore, for odd k, we give a complete structural description of the graphs in Gk that contain no cycle of order less than k. For these graph classes, our results yield efficient recognition algorithms as well as efficient algorithms that determine maximum sets of disjoint paths of order k and minimum sets of vertices intersecting all paths of order k.