Colorful paths for 3-chromatic graphs

DOI10.1016/J.DISC.2017.01.016MaRDI QIDQ512581zbMATH OpenOpenAlexFDO

Authors Stéphane Bessy, Nicolas Bousquet

Publication date 27 February 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

colorful pathvertex coloringrainbow coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: In this paper, we prove that every 3-chromatic connected graph, except $C_7$, admits a 3-vertex coloring in which every vertex is the beginning of a 3-chromatic path. It is a special case of a conjecture due to S.~Akbari, F.~Khaghanpoor, and S.~Moazzeni, cited in [P.J. Cameron, Research problems from the BCC22, emph{Discrete Math.} {�f 311} (2011), 1074--1083], stating that every connected graph $G$ other than $C_7$ admits a $chi(G)$-coloring such that every vertex of $G$ is the beginning of a colorful path (i.e. a path of on $chi(G)$ vertices containing a vertex of each color). We also provide some support for the conjecture in the case of 4-chromatic graphs.

Recommendations

• Rainbow paths with prescribed ends
• Chromatic number of graphs each path of which is 3-colourable
• Optimal colorings with rainbow paths
• Colorful paths in vertex coloring of graphs
• Colorful paths in vertex coloring of graphs.

Cites work

• scientific article; zbMATH DE number 6302978 (Why is no real title available?)
• A colourful path
• A generalization of the Gallai-Roy theorem
• Acyclic graph coloring and the complexity of the star chromatic number
• Circular chromatic number: A survey
• Colorful paths in vertex coloring of graphs
• Colorful paths in vertex coloring of graphs.
• Graph theory
• Independent systems of representatives in weighted graphs
• Optimal colorings with rainbow paths
• Rainbow paths with prescribed ends
• Research problems from the BCC22
• Simple proofs of results on paths representing all colors in proper vertex-colorings
• Triple Systems Not Containing a Fano Configuration

Cited in

(6)

• Colorful paths in vertex coloring of graphs.
• Rainbow paths with prescribed ends
• Chromatic number of graphs each path of which is 3-colourable
• Optimal colorings with rainbow paths
• Colorful paths in vertex coloring of graphs
• Induced colorful trees and paths in large chromatic graphs

This page was built for publication: Colorful paths for 3-chromatic graphs

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