Choosability with union separation

List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For $t\ge k$, a $(k,t)$-list assignment is a list assignment $L$ where $\left|L\left(v\right)\right|\ge k$ for all vertices $v$ and $|L\left(u\right)\cup L\left(v\right)|\ge t$ for all edges $uv$. A graph is $(k,t)$-choosable if there is a proper coloring for every $(k,t)$-list assignment. We explore this concept through examples of graphs that are not $(k,t)$-choosable, demonstrating sparsity conditions that imply a graph is $(k,t)$-choosable, and proving that all planar graphs are $(3,11)$-choosable and $(4,9)$-choosable.     

The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

An interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors. A cyclic interval$t$-coloring of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors of the edges incident with every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w\left(G\right)$ ($w_c\left(G\right)$) and $W\left(G\right)$ ($W_c\left(G\right)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w\left(G\right)$ and $W\left(G\right)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W\left(G\right)\le 1+?\frac{\left|V\left(G\right)\right|}{2}?(\Delta \left(G\right)?1)$. We also give several results towards the general conjecture that $W_c\left(G\right)\le \left|V\left(G\right)\right|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.     

On prisms,Möbius ladders and the cycle space of dense graphs

For a graph $G$, let $\left|G\right|$ denote its number of vertices, $\delta \left(G\right)$ its minimum degree and $Z_1(G;{\mathbb{F}}_2)$ its cycle space. Call a graph Hamilton-generated if and only if every cycle in $G$ is a symmetric difference of some Hamilton circuits of $G$. The main purpose of this paper is to prove: for every $\gamma >0$ there exists $n_0\in \mathbb{Z}$ such that for every graph $G$ with $\left|G\right|⩾n_0$ vertices,

• (1)if $\delta \left(G\right)⩾(\frac{1}{2}+\gamma )\left|G\right|$ and $\left|G\right|$ is odd, then $G$ is Hamilton-generated,
• (2)if $\delta \left(G\right)⩾(\frac{1}{2}+\gamma )\left|G\right|$ and $\left|G\right|$ is even, then the set of all Hamilton circuits of $G$ generates a codimension-one subspace of $Z_1(G;{\mathbb{F}}_2)$ and the set of all circuits of $G$ having length either $\left|G\right|-1$ or $\left|G\right|$ generates all of $Z_1(G;{\mathbb{F}}_2)$,
• (3)if $\delta \left(G\right)⩾(\frac{1}{4}+\gamma )\left|G\right|$ and $G$ is balanced bipartite, then $G$ is Hamilton-generated.

All these degree-conditions are essentially best-possible. The implications in (1) and (2) give an asymptotic affirmative answer to a special case of an open conjecture which according to [I.B.-A. Hartman, Long cycles generate the cycle space of a graph, European J. Combin. 4 (3) (1983) 237–246] originates with A. Bondy.     

Strong list-chromatic index of subcubic graphs

A strong $k$-edge-coloring of a graph G is an edge-coloring with $k$ colors in which every color class is an induced matching. The strong chromatic index of $G$, denoted by ${\chi }_s^{\prime }\left(G\right)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring. In 1985, Erd?s and Ne?et?il conjectured that ${\chi }_s^{\prime }\left(G\right)\le \frac{5}{4}\Delta {\left(G\right)}^2$, where $\Delta \left(G\right)$ is the maximum degree of $G$. When $G$ is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Horák, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.     

Star 5-edge-colorings of subcubic multigraphs

The star chromatic index of a mulitigraph $G$, denoted ${\chi }_s^{\prime }\left(G\right)$, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. A multigraph $G$ is star$k$-edge-colorable if ${\chi }_s^{\prime }\left(G\right)\le k$. Dvo?ák et al. (2013) proved that every subcubic multigraph is star 7-edge-colorable, and conjectured that every subcubic multigraph should be star 6-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than $7∕3$ is star list-5-edge-colorable. It is known that a graph with maximum average degree $14∕5$ is not necessarily star 5-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than $12∕5$ is star 5-edge-colorable.     

Essential edge connectivity of line graphs

Let $G$ be a graph and $L\left(G\right)$ be its line graph. In 1969, Chartrand and Stewart proved that ${\kappa }^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }^{\prime }\left(G\right)?2$, where ${\kappa }^{\prime }\left(G\right)$ and ${\kappa }^{\prime }\left(L\left(G\right)\right)$ denote the edge connectivity of $G$ and $L\left(G\right)$ respectively. We show a similar relationship holds for the essential edge connectivity of $G$ and $L\left(G\right)$, written ${\kappa }_e^{\prime }\left(G\right)$ and ${\kappa }_e^{\prime }\left(L\left(G\right)\right)$, respectively. In this note, it is proved that if $L\left(G\right)$ is not a complete graph and $G$ does not have a vertex of degree two, then ${\kappa }_e^{\prime }\left(L\left(G\right)\right)\ge 2{\kappa }_e^{\prime }\left(G\right)?2$. An immediate corollary is that $\kappa \left(L^2\left(G\right)\right)\ge 2\kappa \left(L\left(G\right)\right)?2$ for such graphs $G$, where the vertex connectivity of the line graph $L\left(G\right)$ and the second iterated line graph $L^2\left(G\right)$ are written as $\kappa \left(L\left(G\right)\right)$ and $\kappa \left(L^2\left(G\right)\right)$ respectively.     

Sum choice number of generalized θ-graphs

Let $G=\left(VE\right)$ be a simple graph and for every vertex $v\in V$ let $L\left(v\right)$ be a set (list) of available colors. $G$ is called $L$-colorable if there is a proper coloring $\phi$ of the vertices with $\phi \left(v\right)\in L\left(v\right)$ for all $v\in V$. A function $f:V\to \mathbb{N}$ is called a choice function of $G$ and $G$ is said to be $f$-list colorable if $G$ is $L$-colorable for every list assignment $L$ choice function is defined by $size\left(f\right)={\sum }_{v\in V}f\left(v\right)$ and the sum choice number ${\chi }_{sc}\left(G\right)$ denotes the minimum size of a choice function of $G$.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For $r\ge 3$ a generalized ${\theta }_{k_1{k}_2\dots k_r}$-graph is a simple graph consisting of two vertices $v_1$ and $v_2$ connected by $r$ internally vertex disjoint paths of lengths $k_1,k_2,\dots ,k_r$ $(k_1\le k_2\le ?\le k_r)$.In 2014, Carraher et al. determined the sum-paintability of all generalized $\theta$-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized $\theta$-graphs with $k_1\ge 2$ and characterize all generalized $\theta$-graphs $G$ which attain the trivial upper bound $\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$.     

On super 2-restricted and 3-restricted edge-connected vertex transitive graphs

Let $G=(V\left(G\right),E\left(G\right))$ be a simple connected graph and $F?E\left(G\right)$. An edge set $F$ is an $m$-restricted edge cut if $G?F$ is disconnected and each component of $G?F$ contains at least $m$ vertices. Let ${\lambda }^{\left(m\right)}\left(G\right)$ be the minimum size of all $m$-restricted edge cuts and ${\xi }_m\left(G\right)=min\{\left|\omega \left(U\right)\right|:\left|U\right|=m\text{ and }G\left[U\right]\text{ is connected}\}$, where $\omega \left(U\right)$ is the set of edges with exactly one end vertex in $U$ and $G\left[U\right]$ is the subgraph of $G$ induced by $U$. A graph $G$ is optimal-${\lambda }^{\left(m\right)}$ if ${\lambda }^{\left(m\right)}\left(G\right)={\xi }_m\left(G\right)$. An optimal-${\lambda }^{\left(m\right)}$ graph is called super $m$-restricted edge-connected if every minimum $m$-restricted edge cut is $\omega \left(U\right)$ for some vertex set $U$ with $\left|U\right|=m$ and $G\left[U\right]$ being connected. In this note, we give a characterization of super 2-restricted edge-connected vertex transitive graphs and obtain a sharp sufficient condition for an optimal-${\lambda }^{\left(3\right)}$ vertex transitive graph to be super 3-restricted edge-connected. In particular, a complete characterization for an optimal-${\lambda }^{\left(2\right)}$ minimal Cayley graph to be super 2-restricted edge-connected is obtained.     

Total list weighting of graphs with bounded maximum average degree

A proper total weighting of a graph $G$ is a mapping $?$ which assigns to each vertex and each edge of $G$ a real number as its weight so that for any edge $uv$ of $G$, ${\sum }_{e\in E\left(v\right)}?\left(e\right)+?\left(v\right)\ne {\sum }_{e\in E\left(u\right)}?\left(e\right)+?\left(u\right)$. A $(k,k^{\prime })$-list assignment of $G$ is a mapping $L$ which assigns to each vertex $v$ a set $L\left(v\right)$ of $k$ permissible weights and to each edge $e$ a set $L\left(e\right)$ of $k^{\prime }$ permissible weights. An $L$-total weighting is a total weighting $?$ with $?\left(z\right)\in L\left(z\right)$ for each $z\in V\left(G\right)\cup E\left(G\right)$. A graph $G$ is called $(k,k^{\prime })$-choosable if for every $(k,k^{\prime })$-list assignment $L$ of $G$, there exists a proper $L$-total weighting. It was proved in Tang and Zhu (2017) that if $p\in \{5,7,11\}$, a graph $G$ without isolated edges and with $\mathrm{mad}\left(G\right)\le p?1$ is $(1,p)$-choosable. In this paper, we strengthen this result by showing that for any prime $p$, a graph $G$ without isolated edges and with $\mathrm{mad}\left(G\right)\le p?1$ is $(1,p)$-choosable.     

A new formula for the decycling number of regular graphs

The decycling number $?\left(G\right)$ of a graph $G$ is the smallest number of vertices which can be removed from $G$ so that the resultant graph contains no cycle. A decycling set containing exactly $?\left(G\right)$ vertices of $G$ is called a $?$-set. For any decycling set $S$ of a $k$-regular graph $G$, we show that $\left|S\right|=\frac{\beta \left(G\right)+m\left(S\right)}{k?1}$, where $\beta \left(G\right)$ is the cycle rank of $G$, $m\left(S\right)=c+\left|E\left(S\right)\right|?1$ is the margin number of $S$, $c$ and $\left|E\left(S\right)\right|$ are, respectively, the number of components of $G?S$ and the number of edges in $G\left[S\right]$. In particular, for any $?$-set $S$ of a 3-regular graph $G$, we prove that $m\left(S\right)=\xi \left(G\right)$, where $\xi \left(G\right)$ is the Betti deficiency of $G$. This implies that the decycling number of a 3-regular graph $G$ is $\frac{\beta \left(G\right)+\xi \left(G\right)}{2}$. Hence $?\left(G\right)=?\frac{\beta \left(G\right)}{2}?$ for a 3-regular upper-embeddable graph $G$, which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute $Z\left(G\right)$, the cardinality of a maximum nonseparating independent set in a $3$-regular graph $G$, which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph $G$, we show that for any $?$-set $S$ of $G$, there exists a spanning tree $T$ of $G$ such that the elements of $S$ are simply the leaves of $T$ with at most two exceptions providing $?\left(G\right)=?\frac{\beta \left(G\right)}{3}?$. On the other hand, if $G$ is a loopless graph on $n$ vertices with maximum degree at most $4$, then

The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006).     

Problems on matchings and independent sets of a graph

Let $G$ be a finite simple graph. For $X?V\left(G\right)$, the difference of $X$, $d\left(X\right)?\left|X\right|?\left|N\left(X\right)\right|$ where $N\left(X\right)$ is the neighborhood of $X$ and $max\{d\left(X\right):X?V\left(G\right)\}$ is called the critical difference of $G$. $X$ is called a critical set if $d\left(X\right)$ equals the critical difference and $\ker \left(G\right)$ is the intersection of all critical sets. $\mathrm{diadem}\left(G\right)$ is the union of all critical independent sets. An independent set $S$ is an inclusion minimal set with$d\left(S\right)>0$ if no proper subset of $S$ has positive difference.A graph $G$ is called a König–Egerváry graph if the sum of its independence number $\alpha \left(G\right)$ and matching number $\mu \left(G\right)$ equals $\left|V\left(G\right)\right|$.In this paper, we prove a conjecture which states that for any graph the number of inclusion minimal independent set $S$ with $d\left(S\right)>0$ is at least the critical difference of the graph.We also give a new short proof of the inequality $\left|\ker \left(G\right)\right|+\left|\mathrm{diadem}\left(G\right)\right|\le 2\alpha \left(G\right)$.A characterization of unicyclic non-König–Egerváry graphs is also presented and a conjecture which states that for such a graph $G$, the critical difference equals $\alpha \left(G\right)?\mu \left(G\right)$, is proved.We also make an observation about $\ker \left(G\right)$ using Edmonds–Gallai Structure Theorem as a concluding remark.     

Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph $G$, denoted ${\chi }_D\left(G\right)$, is defined as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism of $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma$ defined over certain abelian groups $A$ with $\left|A\right|=n$, and show that with probability at least $1?n^{?\Omega (logn)}$, ${\chi }_D\left(\Gamma \right)\le \chi \left(\Gamma \right)+1$.     

List star chromatic index of sparse graphs

A star edge-coloring of a graph $G$ is a proper edge coloring such that every 2-colored connected subgraph of $G$ is a path of length at most 3. For a graph $G$, let the list star chromatic index of $G$, $c{h}_s^{\prime }\left(G\right)$, be the minimum $k$ such that for any $k$-uniform list assignment $L$ for the set of edges, $G$ has a star edge-coloring from $L$. Dvo?ák et al. (2013) asked whether the list star chromatic index of every subcubic graph is at most 7. In Kerdjoudj et al. (2017) we proved that it is at most 8. In this paper we consider graphs with any maximum degree, we proved that if the maximum average degree of a graph $G$ is less than $\frac{14}{5}$ (resp. 3), then $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$ (resp. $c{h}_s^{\prime }\left(G\right)\le 2\Delta \left(G\right)+3$).