BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Mingxian Zhong

Mingxian Zhong appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete Mathematicsmath.COData Structures and Algorithms

Catalog footprint

What is connected

5works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

5 published item(s)

preprint2020arXiv

List-three-coloring $ P_t $-free graphs with no induced 1-subdivision of $ K_{1,s} $

Let $s$ and $t$ be positive integers. We use $P_t$ to denote the path with $t$ vertices and $K_{1,s}$ to denote the complete bipartite graph with parts of size $1$ and $s$ respectively. The one-subdivision of $K_{1,s}$ is obtained by replacing every edge $\{u,v\}$ of $K_{1,s}$ by two edges $\{u,w\}$ and $\{v,w\}$ with a new vertex $w$. In this paper, we give a polynomial-time algorithm for the list-three-coloring problem restricted to the class of $P_t$-free graph with no induced 1-subdivision of $K_{1,s}$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximately coloring graphs without long induced paths

It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on $t$ vertices, for fixed $t$. We propose an algorithm that, given a 3-colorable graph without an induced path on $t$ vertices, computes a coloring with $\max\{5,2\lceil{\frac{t-1}{2}}\rceil-2\}$ many colors. If the input graph is triangle-free, we only need $\max\{4,\lceil{\frac{t-1}{2}}\rceil+1\}$ many colors. The running time of our algorithm is $O((3^{t-2}+t^2)m+n)$ if the input graph has $n$ vertices and $m$ edges.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Three-coloring graphs with no induced seven-vertex path II : using a triangle

In this paper, we give a polynomial time algorithm which determines if a given graph containing a triangle and no induced seven-vertex path is 3-colorable, and gives an explicit coloring if one exists. In previous work, we gave a polynomial time algorithm for three-coloring triangle-free graphs with no induced seven-vertex path. Combined, our work shows that three-coloring a graph with no induced seven-vertex path can be done in polynomial time.

0 citations0 reviewsNo code linkedOpen access