On strong proper connection number of cubic graphs

Author: Huang, F.; Yuan, J.

Description: A path in an edge-colored graph is proper if no two adjacent edges of the path receive the same color. For a connected graph G, the strong proper connection number (SPC number) of G, denoted spc (G), is the minimum number of colors needed to color the edges of G so that every pair of distinct vertices of G is connected by at least one proper geodesic in G. A connected graph G is k-SPC if spc (G) < k. It is implied by the NP-completeness of 3-edge-coloring problem of cubic graphs that the problem to recognize 3-SPC cubic graphs is NP-complete. Then we present in this paper a complete characterization for 2-SPC cubic graphs based on establishing some nice structures of forced branches used in our research. This leads to a linear-time algorithm to recognize 2-SPC cubic graphs. As consequences, for cubic claw-free graphs and cubic bipartite graphs, their SPC numbers can be determined in linear time.

Subject headings: Edge coloring; Strong proper connection number; Cubic graph; Forced edge; Forced branch

Publication year: 2019

Journal or book title: Discrete Applied Mathematics

Volume: 265


Pages: 104-119

Find the full text : https://www.sciencedirect.com/science/article/pii/S0166218X19301775

Find more like this one (cited by): https://scholar.google.com/scholar?cites=14865011840541649087&as_sdt=1000005&sciodt=0,16&hl=en

Type: Journal Article

Serial number: 2991