We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Coloring Graphs to Produce Properly Colored Walks.
- Authors
Melville, Robert; Goddard, Wayne
- 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.
- Subjects
BIPARTITE graphs; GRAPH theory; GEOMETRIC vertices; ANGLES; EDGES (Geometry)
- Publication
Graphs & Combinatorics, 2017, Vol 33, Issue 5, p1271
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-017-1843-y