Algorithms and Discrete Applied Mathematics 6th International Conference, CALDAM 2020, Hyderabad, India, February 13–15, 2020, Proceedings

Vol. 12016. Springer, 2020.

Under the general editorship: M. Changat, S. Das

This book constitutes the proceedings of the 6th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2020, held in Hyderabad, India, in February 2020. The 38 papers presented together with 2 invited talks in this volume were carefully reviewed and selected from 102 submissions. The papers are organized in topical sections on graph algorithms, graph theory, combinatorial optimization, distributed algorithms, combinatorial algorithms, and computational complexity.

Chapters

Smallest 𝐶_{2𝑙+1}-Critical Graphs of Odd-Girth 2𝑘+1

Beaudou L., Foucaud F., Naserasr R., , in: Algorithms and Discrete Applied Mathematics 6th International Conference, CALDAM 2020, Hyderabad, India, February 13–15, 2020, ProceedingsVol. 12016.: Springer, 2020. P. 184–196.

Given a graph H, a graph G is called H-critical if G does not admit a homomorphism to H, but any proper subgraph of G does. Observe that 𝐾𝑘−1-critical graphs are the classic k-(colour)-critical graphs. This work is a first step towards extending questions of extremal nature from k-critical graphs to H-critical graphs. Besides complete ...

Added: February 18, 2020

Keywords: complexity, artificial intelligence, graph theory