On two conjectures about the proper connection number of graphs

DOI10.1016/J.DISC.2017.04.022MaRDI QIDQ2359964zbMATH OpenOpenAlexWikidataFDO

Authors F. Huang, Zhongmei Qin, Colton Magnant, Kenta Ozeki, Xueliang Li

Publication date 23 June 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

2-connected graph3-edge-connected graphdiameterproper connection numberproper-path coloring

Mathematics Subject Classification ID

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

Abstract: A path in an edge-colored graph is called proper if no two consecutive edges of the path receive the same color. For a connected graph $G$, the proper connection number $pc(G)$ of $G$ is defined as the minimum number of colors needed to color its edges so that every pair of distinct vertices of $G$ are connected by at least one proper path in $G$. In this paper, we consider two conjectures on the proper connection number of graphs. The first conjecture states that if $G$ is a noncomplete graph with connectivity $kappa(G)=2$ and minimum degree $delta(G)ge3$, then $pc(G)=2$, posed by Borozan et al.~in [Discrete Math. 312(2012), 2550-2560]. We give a family of counterexamples to disprove this conjecture. However, from a result of Thomassen it follows that 3-edge-connected noncomplete graphs have proper connection number 2. Using this result, we can prove that if $G$ is a 2-connected noncomplete graph with $diam(G)=3$, then $pc(G)=2$, which solves the second conjecture we want to mention, posed by Li and Magnant in [Theory & Appl. Graphs 0(1)(2015), Art.2].

Recommendations

• Minimum degree condition for proper connection number 2
• Proper connection number 2, connectivity, and forbidden subgraphs
• Degree sum conditions for graphs to have proper connection number 2.
• Proper connection of graphs
• Proper connection with many colors

Cites work

• Graph theory
• scientific article; zbMATH DE number 4077268 (Why is no real title available?)
• Minimum degree condition for proper connection number 2
• Minimum degree conditions for the proper connection number of graphs
• On proper-path colorings in graphs
• Proper connection number and connected dominating sets
• Proper connection number of random graphs
• Proper connection numbers of complementary graphs
• Proper connection of graphs
• Rainbow connection in graphs

Cited in

(17)

• Properly colored trails, paths, and bridges
• Minimum degree and size conditions for the proper connection number of graphs
• Conflict-free connection number and independence number of a graph
• Some results on the total proper \(k\)-connection number
• Degree sums and proper connection number of graphs
• Two sufficient conditions for 2-connected graphs to have proper connection number 2
• Optimal proper connection of graphs
• The optimal proper connection number of a graph with given independence number
• Minimum degree condition for proper connection number 2
• Proper connection number 2, connectivity, and forbidden subgraphs
• On the minimum degree and the proper connection number of graphs
• Note on minimum degree and proper connection number
• On the (di)graphs with (directed) proper connection number two
• On the (di)graphs with (directed) proper connection number two
• List proper connection of 2-edge-connected graphs
• Minimum degree and size conditions for the graphs of proper connection number 2
• Complete graphs without proper subgraphs

This page was built for publication: On two conjectures about the proper connection number of graphs

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