Coloring graphs to produce properly colored walks

DOI10.1007/S00373-017-1843-YMaRDI QIDQ1684944zbMATH OpenOpenAlexFDO

Authors Robert Melville, Wayne Goddard

Publication date 12 December 2017

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

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

zbMATH Keywords

edge labelingpath connection numberwalk connection number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: For a connected graph, we define the proper-walk connection number as the minimum number of colors needed to color the edges of a graph so that there is a walk between every pair of vertices without two consecutive edges having the same color. We show that the proper-walk connection number is at most three for all cyclic graphs, and at most two for bridgeless graphs. We also characterize the bipartite graphs that have proper-walk connection number equal to two, and show that this characterization also holds for the analogous problem where one is restricted to properly colored paths.

Review text

Let \(G\) be a connected graph and \(\ell\) an edge labeling. A walk \(W\) or a path \(P\) between two vertices is properly colored with \(\ell\) if any two consecutive edges of \(W\) or \(P\), respectively, have different labels. The proper-walk connection number \(\operatorname{pW}(G)\) of \(G\) is the minimum number of labels needed, such that there exists a properly colored walk between each pair of vertices of \(G\). Similar the proper-path connection number \(\operatorname{pP}(G)\) is defined (by replacing walks with pats). A collection of results on \(\operatorname{pW}(G)\) and \(\operatorname{pP}(G)\) is presented on bipartite graphs, on graphs that contain two edge disjoint odd cycles, on 2-connected graphs, on bridgeless graphs and on unicyclic graphs. The most insight to the topic is provided by the first general result that \(\operatorname{pW}(G)\leq 3\) if \(G\) is a connected graph that different from a tree.

Recommendations

• Proper‐walk connection number of graphs
• Extremal stretch of proper-walk coloring of graphs
• Proper connection with many colors
• On proper-path colorings in graphs
• Proper connection of graphs

Cites work

• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Alternating walks in partially 2-edge-colored graphs and optimal strength of graph labeling
• Directed proper connection of graphs
• On proper-path colorings in graphs
• Proper connection number of random graphs
• Proper connection of graphs

Cited in

(14)

• Conflict-free connections of graphs
• Properly colored trails, paths, and bridges
• Digraphs with proper connection number two
• Proper-walk connection of Hamiltonian digraphs
• A classification of edge-colored graphs based on properly colored walks
• Extremal stretch of proper-walk coloring of graphs
• Proper connection and proper-walk connection of digraphs
• Distributions on graphs and walks
• Green walks in a hypergraph
• On the (di)graphs with (directed) proper connection number two
• Proper‐walk connection number of graphs
• Coloring graphs to produce walks without forbidden repeats
• Cut-through connections of graphs
• On anti-A-connectivity in plane graphs

This page was built for publication: Coloring graphs to produce properly colored walks

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