Author

Lin Tian

View on Semantic Scholar

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Aug 2026

List coloring $C_3$-free planar graphs with a sparse matching of restricted lists

A graph $G$ is $k$-choosable if it has a proper coloring for every $k$-list assignment. While every $C_3$-free planar graph is $4$-choosable, some of them are not $3$-choosable, as constructed by Voigt. Hu and Zhu conjectured that if $G$ is a $C_3$-free planar graph and $X \subseteq V(G)$ induces a bipartite subgraph, then $G$ has a proper $L$-coloring whenever $|L(x)| = 3$ for $x \in X$ and $|L(v)| = 4$ for $v \in V(G) \setminus X$. As evidence, they proved the conjecture when $X$ is an independent set. We provide further evidence by proving the conjecture when the induced subgraph $G[X]$ is an induced sparse matching. This is the first result supporting the conjecture in which the set $X$ receiving smaller lists may induce a subgraph with edges.

S. Hartke, Yu-Pei Li, Joseph Pappe et al. · 0 citations

Preprint Sep 2026

A stronger upper bound on the D-chromatic index

For a graph $G$, a proper edge coloring of $G$ is called a D-coloring if every diamond subgraph of $G$ is rainbow. Let $\chi'_D(G)$ be the D-chromatic index of $G$, which is the smallest integer $k$ such that $G$ admits a D-coloring with $k$ colors. Let $\Delta$ be the maximum degree of $G$. The only known Brooks-type upper bound on $\chi'_D(G)$ is $\frac{9}{16}\Delta^2 + \frac{1}{2}\Delta$, given by a greedy coloring. In this paper, using a probabilistic method, we obtain the first improvement upon this upper bound by proving that $\chi'_D(G) \le (1-c)\frac{9}{16}\Delta^2$ for some $c>0$ and sufficiently large $\Delta$.

Lin Tian, Run-Ze Wang · 0 citations