Optimal colorings with rainbow paths

DOI10.1007/S00373-017-1808-1MaRDI QIDQ2409512zbMATH OpenOpenAlexFDO

Authors Oliver Bendele, Dieter Rautenbach

Publication date 11 October 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.03170

zbMATH Keywords

chromatic numbercircular chromatic numberrainbow path

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40)

Abstract: Let $G$ be a connected graph of chromatic number $k$. For a $k$-coloring $f$ of $G$, a full $f$-rainbow path is a path of order $k$ in $G$ whose vertices are all colored differently by $f$. We show that $G$ has a $k$-coloring $f$ such that every vertex of $G$ lies on a full $f$-rainbow path, which provides a positive answer to a question posed by Lin (Simple proofs of results on paths representing all colors in proper vertex-colorings, Graphs Combin. 23 (2007) 201-203). Furthermore, we show that if $G$ has a cycle of length $k$, then $G$ has a $k$-coloring $f$ such that, for every vertex $u$ of $G$, some full $f$-rainbow path begins at $u$, which solves a problem posed by Bessy and Bousquet (Colorful paths for 3-chromatic graphs, arXiv 1503.00965v1). Finally, we establish some more results on the existence of optimal colorings with (directed) full rainbow paths.

Recommendations

• Rainbow paths with prescribed ends
• Colorful paths in vertex coloring of graphs
• Simple proofs of results on paths representing all colors in proper vertex-colorings
• Rainbow paths
• Colorful paths in vertex coloring of graphs.

Cites work

• Circular chromatic number: A survey
• Colorful paths for 3-chromatic graphs
• Colorful paths in vertex coloring of graphs
• Colorful paths in vertex coloring of graphs.
• Cycles of length 0 modulo 4 in graphs
• scientific article; zbMATH DE number 3257176 (Why is no real title available?)
• Nombre chromatique et plus longs chemins d'un graphe
• Rainbow paths with prescribed ends
• Simple proofs of results on paths representing all colors in proper vertex-colorings
• Star chromatic number

Cited in

(3)

• Colorful paths for 3-chromatic graphs
• Rainbow paths with prescribed ends
• On the complexity of locally rainbow path

This page was built for publication: Optimal colorings with rainbow paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409512)