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

DOI10.1016/j.dam.2019.06.024zbMath1440.05104OpenAlexW2959526340MaRDI QIDQ5918844

Alexandru Popa, Guillaume Ducoffe, Ruxandra Marinescu-Ghemeci

Publication date: 29 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.06.024

zbMATH Keywords

NP-completenessdirected graphsproper connectioneven dicycles

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (4)

Proper-walk connection of Hamiltonian digraphs ⋮ (Strong) proper vertex connection of some digraphs ⋮ Digraphs with proper connection number two ⋮ (Strong) total proper connection of some digraphs

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations of graphs having large proper connection numbers
• Note on vertex and total proper connection numbers
• Proper connection of graphs
• Hardness and algorithms for rainbow connection
• Proper connection number and connected dominating sets
• Proper connection number of random graphs
• Hamiltonian circuits determining the order of chromosomes
• Alternating cycles and paths in edge-coloured multigraphs: A survey
• Coloring graphs to produce properly colored walks
• On (strong) proper vertex-connection of graphs
• A note on finding the bridges of a graph
• A simple test on 2-vertex- and 2-edge-connectivity
• Proper connection with many colors
• Minimum degree conditions for the proper connection number of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On minimal strong blocks
• Rainbow connection in graphs
• Treewidth: Characterizations, Applications, and Computations
• Even dicycles
• Computing Minimal Spanning Subgraphs in Linear Time
• The complexity of satisfiability problems
• On the (di)graphs with (directed) proper connection number two

This page was built for publication: On the (di)graphs with (directed) proper connection number two