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

DOI10.1016/j.endm.2017.10.041zbMath1383.05130OpenAlexW2597804865MaRDI QIDQ5920180

Ruxandra Marinescu-Ghemeci, Alexandru Popa, Guillaume Ducoffe

Publication date: 9 April 2018

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2017.10.041

zbMATH Keywords

bipartiteNP-completenessdigraphsproper connectioneven dicycles

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items

Proper‐walk connection number of graphs, Hardness results for three kinds of colored connections of graphs, Properly colored trails, paths, and bridges, Unnamed Item, Note on directed proper connection number of a random graph, On the (di)graphs with (directed) proper connection number two

Cites Work

• 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
• A note on finding the bridges of a graph
• Proper connection with many colors
• Rainbow connection in graphs
• Even dicycles