Characterizations of graphs G having all [1,k]-factors in kG

Let $k\ge 1$ be an integer and $G$ be a graph. Let $kG$ denote the graph obtained from $G$ by replacing each edge of $G$ with $k$ parallel edges. We say that $G$ has all $[1,k]$-factors or all fractional $[1,k]$-factors if $G$ has an $h$-factor or a fractional $h$-factor for every function $h:V\left(G\right)\to \{1,2,\dots ,k\}$ with $h\left(V\left(G\right)\right)$ even. In this note, we come up with simple characterizations of a graph $G$ such that $kG$ has all $[1,k]$-factors or all fractional $[1,k]$-factors. These characterizations are extensions of Tutte’s 1-Factor Theorem and Tutte’s Fractional 1-Factor Theorem.     

Sharp upper bounds of the spectral radius of a graph

Let $G$ be a simple connected graph with $n$ vertices and $m$ edges. The spectral radius $\rho \left(G\right)$ of $G$ is the largest eigenvalue of its adjacency matrix. In this paper, we firstly consider the effect on the spectral radius of a graph by removing a vertex, and then as an application of the result, we obtain a new sharp upper bound of $\rho \left(G\right)$ which improves some known bounds: If $\frac{(k?2)(k?3)}{2}\le m?n\le \frac{k(k?3)}{2}$, where $k(3\le k\le n)$ is an integer, then $\rho \left(G\right)\le \sqrt{2m?n?k+\frac{5}{2}+\sqrt{2m?2n+\frac{9}{4}}}.$The equality holds if and only if $G$ is a complete graph $K_n$ or $K_4?e$, where $K_4?e$ is the graph obtained from $K_4$ by deleting some edge $e$.     

On the size of special class 1 graphs and (P3;k)-co-critical graphs

A well-known theorem of Vizing states that if G is a simple graph with maximum degree Δ, then the chromatic index ${\chi }^{\prime }(G)$ of G is Δ or $\mathrm{\Delta }+1$. A graph G is class 1 if ${\chi }^{\prime }(G)=\mathrm{\Delta }$, and class 2 if ${\chi }^{\prime }(G)=\mathrm{\Delta }+1$; G is Δ-critical if it is connected, class 2 and ${\chi }^{\prime }(G-e)<{\chi }^{\prime }(G)$ for every $e\in E(G)$. A long-standing conjecture of Vizing from 1968 states that every Δ-critical graph on n vertices has at least $(n(\mathrm{\Delta }-1)+3)/2$ edges. We initiate the study of determining the minimum number of edges of class 1 graphs G, in addition, ${\chi }^{\prime }(G+e)={\chi }^{\prime }(G)+1$ for every $e\in E(\bar{G})$. Such graphs have intimate relation to $(P_3;k)$-co-critical graphs, where a non-complete graph G is $(P_3;k)$-co-critical if there exists a k-coloring of $E(G)$ such that G does not contain a monochromatic copy of $P_3$ but every k-coloring of $E(G+e)$ contains a monochromatic copy of $P_3$ for every $e\in E(\bar{G})$. We use the bound on the size of the aforementioned class 1 graphs to study the minimum number of edges over all $(P_3;k)$-co-critical graphs. We prove that if G is a $(P_3;k)$-co-critical graph on $n\ge k+2$ vertices, then$e(G)\ge \frac{k}{2}(n-\lceil \frac{k}{2}\rceil -\epsilon )+\left(\begin{array}{c}\lceil k/2\rceil +\epsilon \\ 2\end{array}\right),$ where ε is the remainder of $n-\lceil k/2\rceil$ when divided by 2. This bound is best possible for all $k\ge 1$ and $n\ge \lceil 3k/2\rceil +2$.     

Average degrees of edge-chromatic critical graphs

Let $G$ be a simple graph, and let $\Delta \left(G\right)$, $\overline{d}\left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree, the average degree and the chromatic index of $G$, respectively. We called $G$ edge-$\Delta$-critical if ${\chi }^{\prime }\left(G\right)=\Delta \left(G\right)+1$ and ${\chi }^{\prime }\left(H\right)\le \Delta \left(G\right)$ for every proper subgraph $H$ of $G$. Vizing in 1968 conjectured that if $G$ is an edge-$\Delta$-critical graph of order $n$, then $\overline{d}\left(G\right)\ge \Delta \left(G\right)?1+\frac{3}{n}$. We prove that for any edge-$\Delta$-critical graph $G$, $\stackrel{?}{d}\left(G\right)\ge min\left\{\frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1},\frac{3\Delta \left(G\right)}{4}?2\right\},$ that is, $\overline{d}\left(G\right)\ge \left\{\begin{array}{cc}\frac{3}{4}\Delta \left(G\right)?2\hfill & \text{if}\Delta \left(G\right)\le 75;\hfill \\ \frac{2\sqrt{2}\Delta \left(G\right)?3?\sqrt{2}}{2\sqrt{2}+1}\approx 0.7388\Delta \left(G\right)?1.153\hfill & \text{if}\Delta \left(G\right)\ge 76.\hfill \end{array}\right.$This result improves the best known bound $\frac{2}{3}(\Delta \left(G\right)+2)$ obtained by Woodall in 2007 for $\Delta \left(G\right)\ge 41$.     

A local condition for k-contractible edges

An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of the edge results in a $k$-connected graph. For a graph $G$ and a vertex $x$ of $G$, let $G\left[N_G\left(x\right)\right]$ be the subgraph induced by the neighborhood of $x$. We prove that if $G\left[N_G\left(x\right)\right]$ has less than $?\frac{k}{2}?$ edges for any vertex $x$ of a $k$-connected graph $G$, then $G$ has a $k$-contractible edge. We also show that the bound $?\frac{k}{2}?$ is sharp.     

Connected k-dominating graphs

For a graph $G=(V,E)$, the $k$-dominating graph $D_k\left(G\right)$ of $G$ has vertices corresponding to the dominating sets of $G$ having cardinality at most $k$, where two vertices of $D_k\left(G\right)$ are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of $G$ by $\gamma \left(G\right)$ and $\Gamma \left(G\right)$, respectively, and the smallest integer $\epsilon$ for which $D_k\left(G\right)$ is connected for all $k\ge \epsilon$ by $d_0\left(G\right)$. It is known that $\Gamma \left(G\right)+1\le d_0\left(G\right)\le \left|V\right|$, but constructing a graph $G$ such that $d_0\left(G\right)>\Gamma \left(G\right)+1$ appears to be difficult.We present two related constructions. The first construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $G_{k,r}$ such that $\Gamma \left(G_{k,r}\right)=k$, $\gamma \left(G_{k,r}\right)=r+1$ and $d_0\left(G_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)?1$. The second construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $Q_{k,r}$ such that $\Gamma \left(Q_{k,r}\right)=k$, $\gamma \left(Q_{k,r}\right)=r$ and $d_0\left(Q_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)$.     

On coloring numbers of graph powers

The weak $r$-coloring numbers ${\mathrm{wcol}}_r\left(G\right)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $\mathrm{col}\left(G\right)$, and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs.Let $G^p$ denote the $p$th power of $G$. We show that, all integers $p>0$ and $\Delta \ge 3$ and graphs $G$ with $\Delta \left(G\right)\le \Delta$ satisfy $\mathrm{col}\left(G^p\right)\in O\left(p\cdot {\mathrm{wcol}}_{\lceil p∕2\rceil }\left(G\right){(\Delta -1)}^{\lfloor p∕2\rfloor }\right)$; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in $p$. For the square of graphs $G$, we also show that, if the maximum average degree $2k-2<\mathrm{mad}\left(G\right)\le 2k$, then $\mathrm{col}\left(G^2\right)\le (2k-1)\Delta \left(G\right)+2k+1$.     

Note on rainbow cycles in edge-colored graphs

Let G be a graph of order n with an edge-coloring c, and let ${\delta }^c(G)$ denote the minimum color-degree of G. A subgraph F of G is called rainbow if all edges of F have pairwise distinct colors. There have been a lot of results on rainbow cycles of edge-colored graphs. In this paper, we show that (i) if ${\delta }^c(G)>\frac{2n?1}{3}$, then every vertex of G is contained in a rainbow triangle; (ii) if ${\delta }^c(G)>\frac{2n?1}{3}$ and $n\ge 13$, then every vertex of G is contained in a rainbow $C_4$; (iii) if G is complete, $n\ge 7k?17$ and ${\delta }^c(G)>\frac{n?1}{2}+k$, then G contains a rainbow cycle of length at least k, where $k\ge 5$.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

Vertex-disjoint rainbow triangles in edge-colored graphs

Let $G$ be an edge-colored graph of order $n$. The minimum color degree of $G$, denoted by ${\delta }^c\left(G\right)$, is the largest integer $k$ such that for every vertex $v$, there are at least $k$ distinct colors on edges incident to $v$. We say that an edge-colored graph is rainbow if all its edges have different colors. In this paper, we consider vertex-disjoint rainbow triangles in edge-colored graphs. Li (2013) showed that if ${\delta }^c\left(G\right)\ge (n+1)∕2$, then $G$ contains a rainbow triangle and the lower bound is tight. Motivated by this result, we prove that if $n\ge 20$ and ${\delta }^c\left(G\right)\ge (n+2)∕2$, then $G$ contains two vertex-disjoint rainbow triangles. In particular, we conjecture that if ${\delta }^c\left(G\right)\ge (n+k)∕2$, then $G$ contains $k$ vertex-disjoint rainbow triangles. For any integer $k\ge 2$, we show that if $n\ge 16k-12$ and ${\delta }^c\left(G\right)\ge n∕2+k-1$, then $G$ contains $k$ vertex-disjoint rainbow triangles. Moreover, we provide sufficient conditions for the existence of $k$ edge-disjoint rainbow triangles.     

On the (3,1)-choosability of planar graphs without adjacent cycles of length 5,6,7

A $(k,d)$-list assignment $L$ of a graph $G$ is a mapping that assigns to each vertex $v$ a list $L\left(v\right)$ of at least $k$ colors satisfying $|L\left(x\right)\cap L\left(y\right)|\le d$ for each edge $xy$. A graph $G$ is $(k,d)$-choosable if there exists an $L$-coloring of $G$ for every $(k,d)$-list assignment $L$. This concept is also known as choosability with separation. In this paper, we prove that any planar graph $G$ is $(3,1)$-choosable if any $i$-cycle is not adjacent to a $j$-cycle, where $5\le i\le 6$ and $5\le j\le 7$.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.