A proper conflict-free coloring of a graph is a proper vertex coloring in which every non-isolated vertex has a color appearing exactly once in its neighborhood. A graph $G$ is proper conflict-free $(\mathrm{degree}+2)$-choosable if every list assignment $L$ with $|L(v)|\ge d_G(v)+2$ for each $v\in V(G)$ admits such a coloring from the lists. We prove that every graph with girth at least $7$ and maximum average degree less than $8/3$ is proper conflict-free $(\mathrm{degree}+2)$-choosable. Consequently, every planar graph of girth at least $8$ has this property, improving the previously established sufficient girth bound of $9$.
For a graph $G$, a proper coloring of $G$ is called proper conflict-free if for every non-isolated vertex $u$, there is at least one color appearing exactly once in $N_G(u)$. A graph $G$ is proper conflict-free $f$-choosable if for every list assignment $L$ with $|L(v)|\ge f(v)$ for each vertex $v$, $G$ admits a proper...
The Total Coloring Conjecture (TCC) is a challenging unsolved problem posed by Behzad and Vizing independently, which states that every simple graph $G$ admits a ($\Delta(G)$ +2)-total-coloring, where $\Delta(G)$ denotes the maximum degree of $G$. This conjecture has been confirmed for graphs with $\Delta(G)\leq 5$. Ho...
A path in a properly edge-colored graph is rainbow if its edges have pairwise distinct colors. For a proper edge-coloring $c$ of a graph $G$, let $\operatorname{rpc}(G,c)$ be the minimum number of rainbow paths needed to cover $E(G)$, and let $\operatorname{rpc}(G)$ be the maximum of $\operatorname{rpc}(G,c)$ over all...
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,...
S. Hartke, Yu-Pei Li, Joseph Pappe et al.· 0 citations
We prove that there is an absolute constant $c>0$ such that every graph of chromatic number at least $r$ and at most $cr^3\log^2 r$ edges contains at least $\binom r3$ triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any c...
Let $G$ be a graph. Under a strong edge coloring of $G$, every color class is an induced matching. The strong chromatic index of $G$, denoted by $\chi'_s(G)$, is the smallest integer $k$ such that $G$ admits a strong edge coloring with $k$ colors. Denote by $\Delta(G)$ the maximum degree of $G$. In this paper, we prove...
Run-Ze Wang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
