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
We prove that a graph G contains no induced four-edge path and no induced complement of a four-edge path if and only if G is obtained from five-cycles and split graphs by repeatedly applying the following operations: substitution, split graph unification, and split graph unification in the complement ("split graph unification" is a new class-preserving operation that is introduced in this paper).
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.