Monochromatic k-edge-connection colorings of graphs

DOI10.1016/J.DISC.2019.111679zbMATH Open1429.05072arXiv1810.11820OpenAlexW2977370718MaRDI QIDQ2280002FDOQ2280002

Authors: Ping Li, Xueliang Li 

Publication date: 17 December 2019

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

Abstract: A path in an edge-colored graph $G$ is called monochromatic if any two edges on the path have the same color. For $kgeq2$, an edge-colored graph $G$ is said to be monochromatic $k$-edge-connected if every two distinct vertices of $G$ are connected by at least $k$ edge-disjoint monochromatic paths, and $G$ is said to be uniformly monochromatic $k$-edge-connected if every two distinct vertices are connected by at least $k$ edge-disjoint monochromatic paths such that all edges of these $k$ paths colored with a same color. We use $m{c}_k(G)$ and $um{c}_k(G)$ to denote the maximum number of colors that ensures $G$ to be monochromatic $k$-edge-connected and, respectively, $G$ to be uniformly monochromatic $k$-edge-connected. In this paper, we first conjecture that for any $k$-edge-connected graph $G$, $m{c}_k(G)=e(G)-e(H)+lfloorfrack2floor$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$. We verify the conjecture for $k=2$. We also prove the conjecture for $G=K_{k+1}$ when $kgeq4$ is even, and for $G=K_{k,n}$ when $kgeq4$ is even, or when $k=3$ and $ngeqk$. When $G$ is a minimal $k$-edge-connected graph, we give an upper bound of $m{c}_k(G)$, i.e., $m{c}_k(G)leqk-1$, and $m{c}_k(G)leqlfloorfrack2floor$ when $G=K_{k,n}$. For the uniformly monochromatic $k$-edge-connectivity, we prove that for all $k$, $um{c}_k(G)=e(G)-e(H)+1$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$.

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

Recommendations

• Rainbow monochromatic \(k\)-edge-connection colorings of graphs
• Colorful monochromatic connectivity
• Extremal graphs with maximum monochromatic connectivity
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• A note on 2-edge-colorings of complete graphs with small monochromatic \(k\)-connected subgraphs

zbMATH Keywords

edge-coloringedge-connectivitymonochromatic pathuniformly monochromatic \(k\)-edge connection coloring

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A Reduction Method for Edge-Connectivity in Graphs
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• Colorful monochromatic connectivity
• Monochromatic connecting colorings in strongly connected oriented graphs
• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• More on the colorful monochromatic connectivity
• The (vertex-)monochromatic index of a graph
• Total monochromatic connection of graphs
• Cycle systems in the complete bipartite graph minus a one-factor
• Monochromatic connectivity and graph products
• Erdős-Gallai-type results for total monochromatic connection of graphs
• More on total monochromatic connection of graphs.
• Title not available (Why is that?)

Cited In (6)

• Relations of three classes of disconnected coloring
• Colorful monochromatic connectivity
• Monochromatic loose paths in multicolored $k$-uniform cliques
• Rainbow monochromatic \(k\)-edge-connection colorings of graphs
• Monochromatic disconnection of graphs
• Monochromatic \(k\)-connection of graphs

This page was built for publication: Monochromatic \(k\)-edge-connection colorings of graphs

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