Colorful paths for 3-chromatic graphs

DOI10.1016/J.DISC.2017.01.016zbMATH Open1357.05035arXiv1503.00965OpenAlexW2964100562MaRDI QIDQ512581FDOQ512581

Authors: Stéphane Bessy, Nicolas Bousquet 

Publication date: 27 February 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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.

zbMATH Keywords

colorful pathvertex coloringrainbow coloring

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• 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
• Rainbow paths with prescribed ends
• Colorful paths in vertex coloring of 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)