Source author record

Guizhen Liu

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

ResearcherUnclaimed source record

Discrete Mathematics math.CO

Catalog footprint

Research overview

11works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Long properly colored cycles in edge colored complete graphs

Let $K_{n}^{c}$ denote a complete graph on $n$ vertices whose edges are colored in an arbitrary way. Let $Δ^{\mathrm{mon}} (K_{n}^{c})$ denote the maximum number of edges of the same color incident with a vertex of $K_{n}^{c}$ . A properly colored cycle (path) in $K_{n}^{c}$ is a cycle (path) in which adjacent edges have distinct colors. B. Bollobás and P. Erdös (1976) proposed the following conjecture: if $Δ^{\mathrm{mon}} (K_{n}^{c})<\lfloor \frac{n}{2} \rfloor$ , then $K_{n}^{c}$ contains a properly colored Hamiltonian cycle. Li, Wang and Zhou proved that if $Δ^{\mathrm{mon}} (K_{n}^{c})< \lfloor \frac{n}{2} \rfloor$ , then $K_{n}^{c}$ contains a properly colored cycle of length at least $\lceil \frac{n+2}{3}\rceil+1$ . In this paper, we improve the bound to $\lceil \frac{n}{2}\rceil + 2$ .

preprint2013arXiv

On total colorings of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we confirm the total-coloring conjecture for 1-planar graphs with maximum degree at least 13.

preprint2011arXiv

(1,λ)-embedded graphs and the acyclic edge choosability

A (1,λ)-embedded graph is a graph that can be embedded on a surface with Euler characteristic λ so that each edge is crossed by at most one other edge. A graph G is called α-linear if there exists an integral constant β such that e(G') \leq α v(G')+β for each G'\subseteq G. In this paper, it is shown that every (1,λ)-embedded graph G is 4-linear for all possible λ, and is acyclicly edge-(3Δ(G)+70)-choosable for λ=1,2.

preprint2011arXiv

Edge covering pseudo-outerplanar graphs with forests

A graph is called pseudo-outerplanar if each block has an embedding on the plane in such a way that the vertices lie on a fixed circle and the edges lie inside the disk of this circle with each of them crossing at most one another. In this paper, we prove that each pseudo-outerplanar graph admits edge decompositions into a linear forest and an outerplanar graph, or a star forest and an outerplanar graph, or two forests and a matching, or $\max\{Δ(G),4\}$ matchings, or $\max\{\lceilΔ(G)/2\rceil,3\}$ linear forests. These results generalize some ones on outerplanar graphs and $K_{2,3}$ -minor-free graphs, since the class of pseudo-outerplanar graphs is a larger class than the one of $K_{2,3}$ -minor-free graphs.

preprint2011arXiv

Group edge choosability of planar graphs without adjacent short cycles

In this paper, we aim to introduce the group version of edge coloring and list edge coloring, and prove that all 2-degenerate graphs along with some planar graphs without adjacent short cycles is group $(Δ(G)+1)$ -edge-choosable while some planar graphs with large girth and maximum degree is group $Δ(G)$ -edge-choosable.

preprint2011arXiv

k-forested choosability of graphs with bounded maximum average degree

A proper vertex coloring of a simple graph is $k$ -forested if the graph induced by the vertices of any two color classes is a forest with maximum degree less than $k$ . A graph is $k$ -forested $q$ -choosable if for a given list of $q$ colors associated with each vertex $v$ , there exists a $k$ -forested coloring of $G$ such that each vertex receives a color from its own list. In this paper, we prove that the $k$ -forested choosability of a graph with maximum degree $Δ\geq k\geq 4$ is at most $\lceil\fracΔ{k-1}\rceil+1$ , $\lceil\fracΔ{k-1}\rceil+2$ or $\lceil\fracΔ{k-1}\rceil+3$ if its maximum average degree is less than 12/5, $8/3 or 3, respectively.

preprint2011arXiv

List (d,1)-total labelling of graphs embedded in surfaces

The (d,1)-total labelling of graphs was introduced by Havet and Yu. In this paper, we consider the list version of (d,1)-total labelling of graphs. Let G be a graph embedded in a surface with Euler characteristic $ε$ whose maximum degree $Δ(G)$ is sufficiently large. We prove that the (d,1)-total choosability $C_{d,1}^T(G)$ of $G$ is at most $Δ(G)+2d$ .

preprint2011arXiv

List version of ( $p$ ,1)-total labellings

The ( $p$ ,1)-total number $λ_p^T(G)$ of a graph $G$ is the width of the smallest range of integers that suffices to label the vertices and the edges of $G$ such that no two adjacent vertices have the same label, no two incident edges have the same label and the difference between the labels of a vertex and its incident edges is at least $p$ . In this paper we consider the list version. Let $L(x)$ be a list of possible colors for all $x\in V(G)\cup E(G)$ . Define $C_{p,1}^T(G)$ to be the smallest integer $k$ such that for every list assignment with $|L(x)|=k$ for all $x\in V(G)\cup E(G)$ , $G$ has a ( $p$ ,1)-total labelling $c$ such that $c(x)\in L(x)$ for all $x\in V(G)\cup E(G)$ . We call $C_{p,1}^T(G)$ the ( $p$ ,1)-total labelling choosability and $G$ is list $L$ -( $p$ ,1)-total labelable. In this paper, we present a conjecture on the upper bound of $C_{p,1}^T$ . Furthermore, we study this parameter for paths and trees in Section 2. We also prove that $C_{p,1}^T(K_{1,n})\leq n+2p-1$ for star $K_{1,n}$ with $p\geq2, n\geq3$ in Section 3 and $C_{p,1}^T(G)\leq Δ+2p-1$ for outerplanar graph with $Δ\geq p+3$ in Section 4.

preprint2011arXiv

Total coloring of pseudo-outerplanar graphs

A graph is pseudo-outerplanar if each of its blocks has an embedding in the plane so that the vertices lie on a fixed circle and the edges lie inside the disk of this circle with each of them crossing at most one another. In this paper, the total coloring conjecture is completely confirmed for pseudo-outerplanar graphs. In particular, it is proved that the total chromatic number of every pseudo-outerplanar graph with maximum degree $Δ\geq 5$ is $Δ+1$ .

preprint2010arXiv

Edge Coloring of Triangle-Free 1-Planar Graphs

it is shown that each triangle-free 1-planar graph with maximum degree $Δ\geq7$ can be $Δ$ -colorable by Discharging Method.

preprint2010arXiv

Structural properties of 1-planar graphs and an application to acyclic edge coloring

A graph is called 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we establish a local property of 1-planar graphs which describes the structure in the neighborhood of small vertices (i.e. vertices of degree no more than seven). Meanwhile, some new classes of light graphs in 1-planar graphs with the bounded degree are found. Therefore, two open problems presented by Fabrici and Madaras [The structure of 1-planar graphs, Discrete Mathematics, 307, (2007), 854-865] are solved. Furthermore, we prove that each 1-planar graph $G$ with maximum degree $Δ(G)$ is acyclically edge $L$ -choosable where $L=\max\{2Δ(G)-2,Δ(G)+83\}$ .

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.

Guizhen Liu

Research overview

Is this your work?

11 publications

Long properly colored cycles in edge colored complete graphs

On total colorings of 1-planar graphs

(1,λ)-embedded graphs and the acyclic edge choosability

Edge covering pseudo-outerplanar graphs with forests

Group edge choosability of planar graphs without adjacent short cycles

k-forested choosability of graphs with bounded maximum average degree

List (d,1)-total labelling of graphs embedded in surfaces

List version of ( $p$ ,1)-total labellings

Total coloring of pseudo-outerplanar graphs

Edge Coloring of Triangle-Free 1-Planar Graphs

Structural properties of 1-planar graphs and an application to acyclic edge coloring

See the researcher in context

Building this map preview

Guizhen Liu

Research overview

Is this your work?

11 publications

Long properly colored cycles in edge colored complete graphs

On total colorings of 1-planar graphs

(1,λ)-embedded graphs and the acyclic edge choosability

Edge covering pseudo-outerplanar graphs with forests

Group edge choosability of planar graphs without adjacent short cycles

k-forested choosability of graphs with bounded maximum average degree

List (d,1)-total labelling of graphs embedded in surfaces

List version of (ppp,1)-total labellings

Total coloring of pseudo-outerplanar graphs

Edge Coloring of Triangle-Free 1-Planar Graphs

Structural properties of 1-planar graphs and an application to acyclic edge coloring

See the researcher in context

Building this map preview

List version of ( $p$ ,1)-total labellings