Colorful paths in vertex coloring of graphs
type: Item
instance of: scholarly article
title: Colorful paths in vertex coloring of graphs
zbMATH Open document ID: 1290.05070
author: S. Akbari
author: Vahid Liaghat
author: Afshin Nikzad
published in: The Electronic Journal of Combinatorics
publication date: 2011-02-17T00:00:00Z
full work available at URL: v18i1p17.html
review text: Summary: A colorful path in a graph \(G\) is a path with \(\chi(G)\) vertices whose colors are different. A \(v\)-colorful path is such a path, starting from \(v\). Let \(G\neq C_7\) be a connected graph with maximum degree \(\Delta(G)\). We show that there exists a \((\Delta(G)+1)\)-coloring of \(G\) with a \(v\)-colorful path for every \(v\in V(G)\). We also prove that this result is true if one replaces \((\Delta(G)+1)\) colors with \(2\chi(G)\) colors. If \(\chi(G)=\omega(G)\), then the result still holds for \(\chi(G)\) colors. For every graph \(G\), we show that there exists a \(\chi(G)\)-coloring of \(G\) with a rainbow path of length \(\lfloor\chi(G)/2\rfloor\) starting from each \(v \in V(G)\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5852467
zbMATH Keywords: vertex-coloring
zbMATH Keywords: colorful path
zbMATH Keywords: rainbow path
MaRDI profile type: Publication
Recommended article: Colorful paths in vertex coloring of graphs.
Recommended article: From colourful to rainbow paths in graphs: colouring the vertices
Recommended article: Paths and cycles in colored graphs
Recommended article: Q4659605
Recommended article: Q4836076
Recommended article: Colorful paths for 3-chromatic graphs
Recommended article: On proper-path colorings in graphs
Recommended article: Q4901770
Recommended article: Path colorings in bipartite graphs
description: scientific article; zbMATH DE number 5852467