Dynamic list coloring of bipartite graphs

A dynamic coloring of a graph is a proper coloring of its vertices such that every vertex of degree more than one has at least two neighbors with distinct colors. The least number of colors in a dynamic coloring of G, denoted by χ₂(G), is called the dynamic chromatic number of G. The least integer k, such that if every vertex of G is assigned a list of k colors, then G has a proper (resp. dynamic) coloring in which every vertex receives a color from its own list, is called the choice number of G, denoted by ch(G) (resp. the dynamic choice number, denoted by ch₂(G)). It was recently conjectured (Akbari et al. (2009) [1]) that for any graph G, ch₂(G)=max(ch(G),χ₂(G)). In this short note we disprove this conjecture. We first give an example of a small planar bipartite graph G with ch(G)=χ₂(G)=3 and ch₂(G)=4. Then, for any integer k≥5, we construct a bipartite graph G_k such that ch(G_k)=χ₂(G_k)=3 and ch₂(G)≥k.     

On list critical graphs

In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k−1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,…,k−1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2≤p≤k, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph K_nk-list critical. While this is the case for all 5≤k≤n, K_n is not 4-list critical if n is large.     

A note on list edge and list total coloring of planar graphs without adjacent short cycles

LetGbe a planar graph with maximum degreeΔ.In this paper,we prove that if any4-cycle is not adjacent to ani-cycle for anyi∈{3,4}in G,then the list edge chromatic numberχl(G)=Δand the list total chromatic numberχl(G)=Δ+1.     

List 3-dynamic coloring of graphs with small maximum average degree

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that for any vertex $v$, there are at least $min\{r,{deg}_G\left(v\right)\}$ distinct colors in $N_G\left(v\right)$. The $r$-dynamic chromatic number${\chi }_r^d\left(G\right)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$. The list$r$-dynamic chromatic number of a graph $G$ is denoted by $c{h}_r^d\left(G\right)$.Recently, Loeb et al. (0000) showed that the list $3$-dynamic chromatic number of a planar graph is at most 10. And Cheng et al. (0000) studied the maximum average condition to have ${\chi }_3^d\left(G\right)\le 4,5$, or $6$. On the other hand, Song et al. (2016) showed that if $G$ is planar with girth at least 6, then ${\chi }_r^d\left(G\right)\le r+5$ for any $r\ge 3$.In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that $c{h}_3^d\left(G\right)\le 6$ if $mad\left(G\right)<\frac{18}{7}$, $c{h}_3^d\left(G\right)\le 7$ if $mad\left(G\right)<\frac{14}{5}$, and $c{h}_3^d\left(G\right)\le 8$ if $mad\left(G\right)<3$. All of the bounds are tight.     

List coloring of graphs having cycles of length divisible by a given number

Let G be a graph and χ_l(G) denote the list chromatic number of G. In this paper we prove that for every graph G for which the length of each cycle is divisible by l (l≥3), χ_l(G)≤3.     

List star edge coloring of k-degenerate graphs

A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree $\Delta$ is at most $?\frac{3\Delta }{2}?$, which is tight. In this paper, we study the list star edge coloring of $k$-degenerate graphs. Let $c{h}_{st}^{\prime }\left(G\right)$ be the list star chromatic index of $G$: the minimum $s$ such that for every $s$-list assignment $L$ for the edges, $G$ has a star edge coloring from $L$. By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. $c{h}_{st}^{\prime }\left(T\right)\le ?\frac{3\Delta }{2}?$ for any tree $T$ with maximum degree $\Delta$. And then by applying some orientation technique we present two upper bounds for list star chromatic index of $k$-degenerate graphs.     

List coloring of Cartesian products of graphs

A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χ_l(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χ_l(G) and χ_l(H). On the other hand, we prove that χ_l(G×H)?min{χ_l(G)+col(H),col(G)+χ_l(H)}-1 and construct examples of graphs G and H for which our bound is tight.     

Proportional choosability: A new list analogue of equitable coloring

In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A $k$-assignment $L$ for a graph $G$ specifies a list $L\left(v\right)$ of $k$ available colors for each vertex $v$ of $G$. An $L$-coloring assigns a color to each vertex $v$ from its list $L\left(v\right)$. For each color $c$, let $\eta \left(c\right)$ be the number of vertices $v$ whose list $L\left(v\right)$ contains $c$. A proportional$L$-coloring of $G$ is a proper $L$-coloring in which each color $c\in {?}_{v\in V\left(G\right)}L\left(v\right)$ is used $?\eta \left(c\right)∕k?$ or $?\eta \left(c\right)∕k?$ times. A graph $G$ is proportionally$k$-choosable if a proportional $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. We show that if a graph $G$ is proportionally $k$-choosable, then every subgraph of $G$ is also proportionally $k$-choosable and also $G$ is proportionally $(k+1)$-choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph $G$ is proportionally $k$-choosable whenever $k\ge \Delta \left(G\right)+?\left|V\left(G\right)\right|∕2?$, and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques.     

Strong spatial mixing of list coloring of graphs

The property of spatial mixing and strong spatial mixing in spin systems has been of interest because of its implications on uniqueness of Gibbs measures on infinite graphs and efficient approximation of counting problems that are otherwise known to be #P hard. In the context of coloring, strong spatial mixing has been established for Kelly trees in (Ge and Stefankovic, arXiv:1102.2886v3 (2011)) when where q the number of colors, Δ is the degree and .. is the unique solution to . It has also been established in (Goldberg et al., SICOMP 35 (2005) 486–517) for bounded degree lattice graphs whenever for some constant β, where Δ is the maximum vertex degree of the graph. We establish strong spatial mixing for a more general problem, namely list coloring, for arbitrary bounded degree triangle‐free graphs. Our results hold for any whenever the size of the list of each vertex v is at least where is the degree of vertex v and β is a constant that only depends on α. The result is obtained by proving the decay of correlations of marginal probabilities associated with graph nodes measured using a suitably chosen error function. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,599–613, 2015     

Acyclic list 7‐coloring of planar graphs

The acyclic list chromatic number of every planar graph is proved to be at most 7. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 83–90, 2002     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.     

On coloring box graphs

We consider the chromatic number of a family of graphs we call box graphs, which arise from a box complex in n$n$-space. It is straightforward to show that any box graph in the plane has an admissible coloring with three colors, and that any box graph in n$n$-space has an admissible coloring with n+1$n+1$ colors. We show that for box graphs in n$n$-space, if the lengths of the boxes in the corresponding box complex take on no more than two values from the set {1,2,3}$\{1,2,3\}$, then the box graph is 3$3$-colorable, and for some graphs three colors are required. We also show that box graphs in 3-space which do not have cycles of length four (which we call “string complexes”) are 3$3$-colorable.     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

Vertex coloring complete multipartite graphs from random lists of size 2

Let K_s×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of K_s×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all v∈V(K_s×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.     

Hall number for list colorings of graphs: Extremal results

Given a graph G=(V,E) and sets L(v) of allowed colors for each v∈V, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all v∈V and φ(u)≠φ(v) for all uv∈E. The choice number of G is the smallest natural number k admitting a list coloring for G whenever |L(v)|≥k holds for every vertex v. This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3. This estimate is tight for all n. Tightness is deduced from the upper bound that every graph of order n has Hall number at most n−2. We also characterize the cases of equality; for n≥6 these are precisely the graphs whose complements are K₂∪(n−2)K₁, P₄∪(n−4)K₁, and C₅∪(n−5)K₁. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161-182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227-245] as a function of maximum degree.     

On adjacent-vertex-distinguishing total coloring of graphs

In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.