On the (di)graphs with (directed) proper connection number two

Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

A coloring of a graph G is properly connected if every two vertices of G are the ends of a properly colored path. We study the complexity of computing the proper connection number (minimum number of colors in a properly connected coloring) for edge and vertex colorings, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing the strong digraphs with proper arc connection number at most two. Then, we prove that deciding whether a given digraph has proper arc connection number at most two is NP-complete. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper edge connection number at most two.

Original languageEnglish
Pages (from-to)237-242
Number of pages6
JournalElectronic Notes in Discrete Mathematics
Volume62
DOIs
Publication statusPublished - Nov 2017

Keywords

  • NP-complete
  • bipartite
  • digraphs
  • even dicycles
  • proper connection

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On the (di)graphs with (directed) proper connection number two'. Together they form a unique fingerprint.

Cite this