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.     

Injective colorings of sparse graphs

Let denote the maximum average degree (over all subgraphs) of G and let χ_i(G) denote the injective chromatic number of G. We prove that if , then χ_i(G)≤Δ(G)+1; and if , then χ_i(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χ_i(G)≤Δ(G)+1; similarly, if g(G)≥13, then χ_i(G)=Δ(G).     

List r-hued chromatic number of graphs with bounded maximum average degrees

For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring $c$ with at most $k$ colors such that for any vertex $v$ with degree $d\left(v\right)$, there are at least min$\{d\left(v\right),r\}$ different colors present at the neighborhood of $v$. The $r$-hued chromatic number of $G$, ${\chi }_r\left(G\right)$, is the least integer $k$ such that a $(k,r)$-coloring of $G$ exists. The list$r$-hued chromatic number${\chi }_{L,r}\left(G\right)$ of $G$ is similarly defined. Thus if $\Delta \left(G\right)\ge r$, then ${\chi }_{L,r}\left(G\right)\ge {\chi }_r\left(G\right)\ge r+1$. We present examples to show that, for any sufficiently large integer $r$, there exist graphs with maximum average degree less than 3 that cannot be $(r+1,r)$-colored. We prove that, for any fraction $q<\frac{14}{5}$, there exists an integer $R=R\left(q\right)$ such that for each $r\ge R$, every graph $G$ with maximum average degree $q$ is list $(r+1,r)$-colorable. We present examples to show that for some $r$ there exist graphs with maximum average degree less than 4 that cannot be $r$-hued colored with less than $\frac{3r}{2}$ colors. We prove that, for any sufficiently small real number $?>0$, there exists an integer $h=h\left(?\right)$ such that every graph $G$ with maximum average degree $4??$ satisfies ${\chi }_{L,r}\left(G\right)\le r+h\left(?\right)$. These results extend former results in Bonamy et al. (2014).     

Upper Bounds on List Star Chromatic Index of Sparse Graphs

A star k-edge-coloring is a proper k-edge-coloring such that every connected bicolored subgraph is a path of length at most 3.The star chromatic indexχ'_st(G)of a graph G is the smallest integer k such that G has a star k-edge-coloring.The list star chromatic index ch'st(G)is defined analogously.The star edge coloring problem is known to be NP-complete,and it is even hard to obtain tight upper bound as it is unknown whether the star chromatic index for complete graph is linear or super linear.In this paper,we study,in contrast,the best linear upper bound for sparse graph classes.We show that for everyε>0 there exists a constant c(ε)such that if mad(G)<8/3-ε,then■and the coefficient 3/2 ofΔis the best possible.The proof applies a newly developed coloring extension method by assigning color sets with different sizes.     

Linear choosability of sparse graphs

A linear coloring is a proper coloring such that each pair of color classes induces a union of disjoint paths. We study the linear list chromatic number, denoted , of sparse graphs. The maximum average degree of a graph G, denoted mad(G), is the maximum of the average degrees of all subgraphs of G. It is clear that any graph G with maximum degree Δ(G) satisfies . In this paper, we prove the following results: (1) if and Δ(G)≥3, then , and we give an infinite family of examples to show that this result is best possible; (2) if and Δ(G)≥9, then , and we give an infinite family of examples to show that the bound on cannot be increased in general; (3) if G is planar and has girth at least 5, then .     

Edge-partitions of graphs and their neighbor-distinguishing index

A proper edge coloring is neighbor-distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The minimum number of colors needed for a neighbor-distinguishing edge coloring is the neighbor-distinguishing index, denoted by ${\chi }_a^{\prime }\left(G\right)$. A graph is normal if it contains no isolated edges. Let $G$ be a normal graph, and let $\Delta \left(G\right)$ and ${\chi }^{\prime }\left(G\right)$ denote the maximum degree and the chromatic index of $G$, respectively. We modify the previously known techniques of edge-partitioning to prove that ${\chi }_a^{\prime }\left(G\right)\le 2{\chi }^{\prime }\left(G\right)$, which implies that ${\chi }_a^{\prime }\left(G\right)\le 2\Delta \left(G\right)+2$. This improves the result in Wang et al. (2015), which states that ${\chi }_a^{\prime }\left(G\right)\le \frac{5}{2}\Delta \left(G\right)$ for any normal graph. We also prove that ${\chi }_a^{\prime }\left(G\right)\le 2\Delta \left(G\right)$ when $\Delta \left(G\right)=2^k$, $k$ is an integer with $k\ge 2$.     

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.     

Star chromatic index of subcubic multigraphs

The star chromatic index of a multigraph G, denoted , is the minimum number of colors needed to properly color the edges of G such that no path or cycle of length four is bicolored. A multigraph G is star k‐edge‐colorable if . Dvořák, Mohar, and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313–326] proved that every subcubic multigraph is star 7‐edge‐colorable. They conjectured in the same article that every subcubic multigraph should be star 6‐edge‐colorable. In this article, we first prove that it is NP‐complete to determine whether for an arbitrary graph G. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs G with such that but for any , where . We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph G is star 6‐edge‐colorable if , and star 5‐edge‐colorable if , respectively, where is the maximum average degree of a multigraph G. This partially confirms the conjecture of Dvořák, Mohar, and Šámal.     

An improved upper bound on the adjacent vertex distinguishing total chromatic number of graphs

An adjacent vertex distinguishing total $k$-coloring of a graph $G$ is a proper total $k$-coloring of $G$ such that any pair of adjacent vertices have different sets of colors. The minimum number $k$ needed for such a total coloring of $G$ is denoted by ${\chi }_a^{\prime \prime }\left(G\right)$. In this paper we prove that ${\chi }_a^{\prime \prime }\left(G\right)\le 2\Delta \left(G\right)?1$ if $\Delta \left(G\right)\ge 4$, and ${\chi }_a^{\prime \prime }\left(G\right)\le ?\frac{5\Delta \left(G\right)+8}{3}?$ in general. This improves a result in Huang et al. (2012) which states that ${\chi }_a^{\prime \prime }\left(G\right)\le 2\Delta \left(G\right)$ for any graph with $\Delta \left(G\right)\ge 3$.     

On the oriented chromatic number of graphs with given excess

The excess of a graph G is defined as the minimum number of edges that must be deleted from G in order to get a forest. We prove that every graph with excess at most k has chromatic number at most and that this bound is tight. Moreover, we prove that the oriented chromatic number of any graph with excess k is at most k+3, except for graphs having excess 1 and containing a directed cycle on 5 vertices which have oriented chromatic number 5. This bound is tight for k?4.     

The strong chromatic index of a class of graphs

The strong chromatic index of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings. Faudree et al. [R.J. Faudree, R.H. Schelp, A. Gyárfás, Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211] proposed an open problem: If G is bipartite and if for each edge xy∈E(G), d(x)+d(y)≤5, then sχ^′(G)≤6. Let H₀ be the graph obtained from a 5-cycle by adding a new vertex and joining it to two nonadjacent vertices of the 5-cycle. In this paper, we show that if G (not necessarily bipartite) is not isomorphic to H₀ and d(x)+d(y)≤5 for any edge xy of G then sχ^′(G)≤6. The proof of the result implies a linear time algorithm to produce a strong edge coloring using at most 6 colors for such graphs.     

On circle graphs with girth at least five

Circle graphs with girth at least five are known to be 2-degenerate [A.A. Ageev, Every circle graph with girth at least 5 is 3-colourable, Discrete Math. 195 (1999) 229-233]. In this paper, we prove that circle graphs with girth at least g≥5 and minimum degree at least two contain a chain of g−4 vertices of degree two, which implies Ageev’s result in the case g=5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g≥5 as well as a precise estimate of their maximum average degree.     

没有K4-图子式的图的无圈边色数

一个图G 的无圈k- 边染色是指G 的一个正常的不产生双色圈的k- 边染色. G 的无圈边色数a′(G) 定义为使得G 有一个无圈k- 边染色的最小的整数k. 本文完全刻画了最大度不为4 的没有K₄-图子式的图的无圈边色数.