The optimal proper connection number of a graph with given independence number

DOI10.1016/j.disopt.2021.100660zbMath1506.05109arXiv2003.08779OpenAlexW3185928135MaRDI QIDQ2234746

Boram Park, Shinya Fujita

Publication date: 19 October 2021

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

independence numberedge-colored graphoptimal proper connection numberproperly connected graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Cites Work

• Unnamed Item
• Generalized Ramsey numbers for graphs with three disjoint cycles versus a complete graph
• Proper connection of graphs
• Longest cycles in \(k\)-connected graphs with given independence number
• Independence number and vertex-disjoint cycles
• Proper connection number and connected dominating sets
• Proper connection number of random graphs
• Hamiltonian circuits determining the order of chromosomes
• Highly connected subgraphs of graphs with given independence number
• Optimal proper connection of graphs
• On two conjectures about the proper connection number of graphs
• Proper connection with many colors
• Minimum degree conditions for the proper connection number of graphs
• Upper bounds of proper connection number of graphs
• A note on Hamiltonian circuits

This page was built for publication: The optimal proper connection number of a graph with given independence number