BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let s and t be positive integers. We use Pt to denote the path with t vertices and K1,s to denote the complete bipartite graph with parts of size 1 and s respectively. The one-subdivision of K1,s is obtained by replacing every edge {u,v} of K1,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 Pt-free graph with no induced 1-subdivision of K1,s.
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⌈2t−1⌉−2} many colors. If the input graph is triangle-free, we only need max{4,⌈2t−1⌉+1} many colors. The running time of our algorithm is O((3t−2+t2)m+n) if the input graph has n vertices and m edges.
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.
We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle C5 and no induced 6-vertex path P6.
In this paper, we give a polynomial time algorithm which determines if a given triangle-free graph with no induced seven-vertex path is 3-colorable, and gives an explicit coloring if one exists.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.