Combinatorics and Graph Theory

2007 Submissions

[2] viXra:2007.0111 [pdf] submitted on 2020-07-15 03:01:17

On the Coloring of Efl Graph Using Colors Equal to Size of Maximal Clique

Authors: Prajnanaswaroopa S
Comments: 4 Pages. Comments are welcome

In this short note, we give a proof for the fact that the chromatic number of the EFL graph formed by the adjoining of k cliques such that any two cliques share at most one vertex is k
Category: Combinatorics and Graph Theory

[1] viXra:2007.0057 [pdf] replaced on 2020-07-18 17:19:17

Solving the 106 Years Old 3^k Points Problem with the Clockwise-Algorithm

Authors: Marco Ripà
Comments: Pages.

In this paper, we present the clockwise-algorithm that solves the extension in k-dimensions of the infamous nine-dot problem, the well known two-dimensional thinking outside the box puzzle. We describe a general strategy that constructively produces minimum length covering trails, for any k∈N−{0}, solving the NP-complete (3×3×⋯×3)-points problem inside a 3×3×⋯×3 hypercube. In particular, using our algorithm, we explicitly draw different covering trails of minimal length h(k) = (3^k − 1)/2, for k = 3, 4, 5. Furthermore, we conjecture that, for every k ≥ 1, it is possible to solve the 3^k-points problem with h(k) lines starting from any of the 3^k nodes, except from the central one. Finally, we cover 3×3×3 points with a tree of size 12.
Category: Combinatorics and Graph Theory