Source author record

Yingli Kang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

(1,0,0)-colorability of planar graphs without cycles of length 4 or 6

A graph $G$ is $(d_1,d_2,d_3)$ -colorable if the vertex set $V(G)$ can be partitioned into three subsets $V_1,V_2$ and $V_3$ such that for $i\in\{1,2,3\}$ , the induced graph $G[V_i]$ has maximum vertex-degree at most $d_i$ . So, $(0,0,0)$ -colorability is exactly 3-colorability. The well-known Steinberg's conjecture states that every planar graph without cycles of length 4 or 5 is 3-colorable. As this conjecture being disproved by Cohen-Addad etc. in 2017, a similar question, whether every planar graph without cycles of length 4 or $i$ is 3-colorable for a given $i\in \{6,\ldots,9\}$ , is gaining more and more interest. In this paper, we consider this question for the case $i=6$ from the viewpoint of improper colorings. More precisely, we prove that every planar graph without cycles of length 4 or 6 is (1,0,0)-colorable, which improves on earlier results that they are (2,0,0)-colorable and also (1,1,0)-colorable, and on the result that planar graphs without cycles of length from 4 to 6 are (1,0,0)-colorable.

preprint2016arXiv

Face-degree bounds for planar critical graphs

The only remaining case of a well known conjecture of Vizing states that there is no planar graph with maximum degree 6 and edge chromatic number 7. We introduce parameters for planar graphs, based on the degrees of the faces, and study the question whether there are upper bounds for these parameters for planar edge-chromatic critical graphs. Our results provide upper bounds on these parameters for smallest counterexamples to Vizing's conjecture, thus providing a partial characterization of such graphs, if they exist. For $k \leq 5$ the results give insights into the structure of planar edge-chromatic critical graphs.

preprint2015arXiv

Circular coloring of signed graphs

Let $k, d$ ( $2d \leq k)$ be two positive integers. We generalize the well studied notions of $(k,d)$ -colorings and of the circular chromatic number $χ_c$ to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number $χ$ . Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on $n$ vertices, if the difference is smaller than 1, then there exists $ε_n>0$ , such that the difference is at most $1 - ε_n$ . We also show that notion of $(k,d)$ -colorings is equivalent to $r$ -colorings (see (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26, Springer Berlin Heidelberg (2006) 497-550)).

preprint2015arXiv

The chromatic spectrum of signed graphs

The chromatic number $χ((G,σ))$ of a signed graph $(G,σ)$ is the smallest number $k$ for which there is a function $c : V(G) \rightarrow \mathbb{Z}_k$ such that $c(v) \not= σ(e) c(w)$ for every edge $e = vw$ . Let $Σ(G)$ be the set of all signatures of $G$ . We study the chromatic spectrum $Σ_χ(G) = \{χ((G,σ))\colon\ σ\in Σ(G)\}$ of $(G,σ)$ . Let $M_χ(G) = \max\{χ((G,σ))\colon\ σ\in Σ(G)\}$ , and $m_χ(G) = \min\{χ((G,σ))\colon\ σ\in Σ(G)\}$ . We show that $Σ_χ(G) = \{k : m_χ(G) \leq k \leq M_χ(G)\}$ . We also prove some basic facts for critical graphs. Analogous results are obtained for a notion of vertex-coloring of signed graphs which was introduced by Máčajová, Raspaud, and Škoviera.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.