Rainbow paths with prescribed ends

Publication: Research - peer-reviewJournal article – Annual report year: 2011

Documents

View graph of relations

It was conjectured in [S. Akbari, F. Khaghanpoor, and S. Moazzeni. Colorful paths in vertex coloring of graphs. Preprint] that, if G is a connected graph distinct from C-7, then there is a chi(G)-coloring of G in which every vertex v is an element of V(G) is an initial vertex of a path P with chi(G) vertices whose colors are different. In[S. Akbari, V. Liaghat, and A. Nikzad. Colorful paths in vertex coloring of graphs. Electron. J. Combin. 18(1):P17, 9pp, 2011] this was proved with left perpendicular chi(G)/2right perpendicular vertices instead of chi(G) vertices. We strengthen this to chi(G) - 1 vertices. We also prove that every connected graph with atleast one edge has a proper k-coloring (for some k) such that every vertex of color i has a neighbor of color i + 1 (mod k). C-5 shows that k may have to be greater than the chromatic number. However, if the graph is connected, infinite and locally finite, and has finite chromatic number, then the k-coloring exists for every k >= chi(G). In fact, the k-coloring can be chosen such that every vertex is a starting vertex of an infinite path such that the color increases by 1 (mod k) along each edge. The method is based on the circular chromatic number chi(c)(G). In particular, we verify the above conjecture for all connected graphs whose circular chromatic number equals the chromatic number.
Original languageEnglish
JournalThe Electronic Journal of Combinatorics
Volume18
Issue number1
Pages (from-to)P86
ISSN1077-8926
StatePublished - 2011
Peer-reviewedYes

Keywords

  • Rainbow path, Circular coloring, Chromatic number
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 6291569