More on the k-color connection number of a graph

arXiv1703.09378MaRDI QIDQ6284864FDOQ6284864

Authors: Hong Chang, Zhong Huang, Xueliang Li 

Publication date: 27 March 2017

Abstract: An edge-colored graph $G$ is $k$-color connected if, between each pair of vertices, there exists a path using at least $k$ different colors. The $k$-color connection number of $G$, denoted by $c{c}_k(G)$, is the minimum number of colors needed to color the edges of $G$ so that $G$ is $k$-color connected. First, we prove that let $H$ be a subdivision of a connected graph $G$, then $c{c}_k(H)leqc{c}_k(G)$. Second, we give sufficient conditions to guarantee that $c{c}_k(G)=k$ in terms of minimum degree and the number of edges for 2-connected graphs. As a byproduct, we show that almost all graphs have the $k$-color connection number $k$. At last, we investigate the relationship between the $k$-color connection number and the rainbow connection number for a connected graph. In addition, we give exact values of $k$-color connection numbers for some graph classes: subdivisions of the wheel and the complete graph, and the generalised $heta$-graph.

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

This page was built for publication: More on the $k$-color connection number of a graph

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