Antimagic orientation of Halin graphs

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$ such that all $n$ oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.     

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.     

Strong edge-coloring for planar graphs with large girth

A strong edge-coloring of a graph $G=(V,E)$ is a partition of its edge set $E$ into induced matchings. Let $G$ be a connected planar graph with girth $k\ge 26$ and maximum degree $\Delta$. We show that either $G$ is isomorphic to a subgraph of a very special $\Delta$-regular graph with girth $k$, or $G$ has a strong edge-coloring using at most $2\Delta +\lceil \frac{12(\Delta -2)}{k}\rceil$ colors.     

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.     

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.     

Antimagic orientations of disconnected even regular graphs

A $labeling$ of a digraph $D$ with $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$. A labeling of $D$ is $antimagic$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u\in V\left(D\right)$ for a labeling is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. An orientation $D$ of a graph $G$ is $antimagic$ if $D$ has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2$d$-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2$d$-regular graphs with more than two odd components. We show that every 2$d$-regular graph with $k(3\le k\le 5d+4)$ odd components has an antimagic orientation. And we show that each 2$d$-regular graph with $k(k\ge 5d+5)$ odd components admits an antimagic orientation if each odd component has at least $2x_0+5$ vertices with $x_0=?\frac{k?(5d+4)}{2d?2}?$.     

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.     

A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

Two-pebbling and odd-two-pebbling are not equivalent

Let $G$ be a connected graph. A configuration of pebbles assigns a nonnegative integer number of pebbles to each vertex of $G$. A move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if any vertex can get at least one pebble through a sequence of moves. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)-q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of moves so that at least two pebbles can be placed on any vertex. A graph has the odd-two-pebbling property if after placing more than $2\pi \left(G\right)-r$ pebbles on $G$, where $r$ is the number of vertices with an odd number of pebbles, there is a sequence of moves so that at least two pebbles can be placed on any vertex. In this paper, we prove that the two-pebbling and odd-two-pebbling properties are not equivalent.     

Domination versus total domination in claw-free cubic graphs

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, every vertex in S is adjacent to some other vertex in S, then S is a total dominating set. The domination number $\gamma (G)$ of G is the minimum cardinality of a dominating set in G, while the total domination number ${\gamma }_t(G)$ of G is the minimum cardinality of total dominating set in G. A claw-free graph is a graph that does not contain $K_{1,3}$ as an induced subgraph. Let G be a connected, claw-free, cubic graph of order n. We show that if we exclude two graphs, then $\frac{{\gamma }_t(G)}{\gamma (G)}\le \frac{12}{7}$, and this bound is best possible. In order to prove this result, we prove that if we exclude four graphs, then ${\gamma }_t(G)\le \frac{3}{7}n$, and this bound is best possible. These bounds improve previously best known results due to Favaron and Henning (2008) [7], Southey and Henning (2010) [19].     

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.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

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

A note on the weak (2,2)-Conjecture

Let $G=(V,E)$ be any graph without isolated edges. The well known 1–2–3 Conjecture asserts that the edges of $G$ can be weighted with $1,2,3$ so that adjacent vertices have distinct weighted degrees, i.e. the sums of their incident weights. It was independently conjectured that if $G$ additionally has no isolated triangles, then it can be edge decomposed into two subgraphs $G_1,G_2$ which fulfil the 1–2–3 Conjecture with just weights 1,2, i.e. such that there exist weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ so that for every $uv\in E$, if $uv\in E\left(G_i\right)$ then $d_{{\omega }_i}\left(u\right)\ne d_{{\omega }_i}\left(v\right)$, where $d_{{\omega }_i}\left(v\right)$ denotes the sum of weights incident with $v\in V$ in $G_i$ for $i=1,2$. We apply the probabilistic method to prove that the known weakening of this so-called Standard (2,2)-Conjecture holds for graphs with minimum degree large enough. Namely, we prove that if $\delta \left(G\right)\ge 3660$, then $G$ can be decomposed into graphs $G_1,G_2$ for which weightings ${\omega }_i:E\left(G_i\right)\to \{1,2\}$ exist so that for every $uv\in E$, $d_{{\omega }_1}\left(u\right)\ne d_{{\omega }_1}\left(v\right)$ or $d_{{\omega }_2}\left(u\right)\ne d_{{\omega }_2}\left(v\right)$. In fact we prove a stronger result, as one of the weightings is redundant, i.e. uses just weight 1.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.