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

Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci, Alexandru Popa

Research output: Contribution to journalArticle

Abstract

The (directed) proper connection number of a given (di)graph G is the least number of colors needed to edge-color G such that there exists a properly colored (di)path between every two vertices in G. There also exist vertex-coloring versions of the proper connection number in (di)graphs. We initiate the study of the complexity of computing the proper connection number and (two variants of) the proper vertex connection number, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing strong digraphs with directed proper connection number at most two. In particular, we prove that deciding whether a given digraph has directed proper connection number at most two is NP-complete. Furthermore, we show that there are infinitely many such digraphs without an even-length dicycle. To the best of our knowledge, the proper vertex connection number of digraphs has not been studied before. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, on a more positive side we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper connection number at most two.

Original languageEnglish
JournalDiscrete Applied Mathematics
DOIs
Publication statusPublished - Jan 1 2019

Fingerprint

Color
Directed graphs
Digraph
Coloring
Graph in graph theory
Polynomials
Vertex Connectivity
Bounded Treewidth
Vertex Coloring
Disprove
Recognition Algorithm
Vertex of a graph
Undirected Graph
Bipartite Graph
Directed Graph
Polynomial-time Algorithm
Arc of a curve
NP-complete problem
Path
Computing

Keywords

  • Directed graphs
  • Even dicycles
  • NP-complete
  • Proper connection

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this

On the (di)graphs with (directed) proper connection number two. / Ducoffe, Guillaume; Marinescu-Ghemeci, Ruxandra; Popa, Alexandru.

In: Discrete Applied Mathematics, 01.01.2019.

Research output: Contribution to journalArticle

Ducoffe, Guillaume ; Marinescu-Ghemeci, Ruxandra ; Popa, Alexandru. / On the (di)graphs with (directed) proper connection number two. In: Discrete Applied Mathematics. 2019.
@article{3cac8b7fda2147828b634714e1766988,
title = "On the (di)graphs with (directed) proper connection number two",
abstract = "The (directed) proper connection number of a given (di)graph G is the least number of colors needed to edge-color G such that there exists a properly colored (di)path between every two vertices in G. There also exist vertex-coloring versions of the proper connection number in (di)graphs. We initiate the study of the complexity of computing the proper connection number and (two variants of) the proper vertex connection number, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing strong digraphs with directed proper connection number at most two. In particular, we prove that deciding whether a given digraph has directed proper connection number at most two is NP-complete. Furthermore, we show that there are infinitely many such digraphs without an even-length dicycle. To the best of our knowledge, the proper vertex connection number of digraphs has not been studied before. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, on a more positive side we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper connection number at most two.",
keywords = "Directed graphs, Even dicycles, NP-complete, Proper connection",
author = "Guillaume Ducoffe and Ruxandra Marinescu-Ghemeci and Alexandru Popa",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.dam.2019.06.024",
language = "English",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

TY - JOUR

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

AU - Ducoffe, Guillaume

AU - Marinescu-Ghemeci, Ruxandra

AU - Popa, Alexandru

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The (directed) proper connection number of a given (di)graph G is the least number of colors needed to edge-color G such that there exists a properly colored (di)path between every two vertices in G. There also exist vertex-coloring versions of the proper connection number in (di)graphs. We initiate the study of the complexity of computing the proper connection number and (two variants of) the proper vertex connection number, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing strong digraphs with directed proper connection number at most two. In particular, we prove that deciding whether a given digraph has directed proper connection number at most two is NP-complete. Furthermore, we show that there are infinitely many such digraphs without an even-length dicycle. To the best of our knowledge, the proper vertex connection number of digraphs has not been studied before. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, on a more positive side we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper connection number at most two.

AB - The (directed) proper connection number of a given (di)graph G is the least number of colors needed to edge-color G such that there exists a properly colored (di)path between every two vertices in G. There also exist vertex-coloring versions of the proper connection number in (di)graphs. We initiate the study of the complexity of computing the proper connection number and (two variants of) the proper vertex connection number, in undirected and directed graphs, respectively. First we disprove some conjectures of Magnant et al. (2016) on characterizing strong digraphs with directed proper connection number at most two. In particular, we prove that deciding whether a given digraph has directed proper connection number at most two is NP-complete. Furthermore, we show that there are infinitely many such digraphs without an even-length dicycle. To the best of our knowledge, the proper vertex connection number of digraphs has not been studied before. We initiate the study of proper vertex connectivity in digraphs and we prove similar results as for the arc version. Finally, on a more positive side we present polynomial-time recognition algorithms for bounded-treewidth graphs and bipartite graphs with proper connection number at most two.

KW - Directed graphs

KW - Even dicycles

KW - NP-complete

KW - Proper connection

UR - http://www.scopus.com/inward/record.url?scp=85068509645&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068509645&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.06.024

DO - 10.1016/j.dam.2019.06.024

M3 - Article

AN - SCOPUS:85068509645

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -