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
A graph is called 2K2-free if it does not contain two independent edges as an induced subgraph. Mou and Pasechnik conjectured that every 23-tough 2K2-free graph with at least three vertices has a spanning trail with maximum degree at most 4. In this paper, we confirm this conjecture. We also provide examples for all t<45 of t-tough graphs that do not have a spanning trail with maximum degree at most 4.
In this paper, we consider coloring of graphs under the assumption that some vertices are already colored. Let G be an r-colorable graph and let P⊂V(G). Albertson [J.\ Combin.\ Theory Ser. B \textbf{73} (1998), 189--194] has proved that if every pair of vertices in P have distance at least four, then every (r+1)-coloring of G[P] can be extended to an (r+1)-coloring of G, where G[P] is the subgraph of G induced by P. In this paper, we allow P to have pairs of vertices of distance at most three, and investigate how the number of such pairs affects the number of colors we need to extend the coloring of G[P]. We also study the effect of pairs of vertices of distance at most two, and extend the result by Albertson and Moore [J.\ Combin.\ Theory Ser. B \textbf{77} (1999) 83--95].
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.