Perfect Folding of Graphs

E. M. El-Kholy; H. Ahmed

Authors

E. M. El-Kholy
H. Ahmed

clique number, chromatic number, perfect graphs, graph folding

Abstract

In this paper we introduced the definition of perfect folding of graphs and we proved that cycle graphs of even number of edges can be perfectly folded while that of odd number of edges can be perfectly folded to C3. Also we proved that wheel graphs of odd number of vertices can be perfectly folded to C3. Finally we proved that if G is a graph of n vertices such that 2 > clique number = chromatic number = k > n, then the graph can be perfectly folded to a clique of order k.

Downloads

How to Cite

Perfect Folding of Graphs. (2021). Global Journal of Science Frontier Research, 21(F1), 7-15. https://journalofscience.org/index.php/GJSFR/article/view/2887

Download Citation

References

Béla Bollobás, Douglas West (2000) A note on generalized chromatic number and generalized girth. 213(1-3), 29-34.

R Balakrishnan, K Ranganathan (1991) Graph Colorings. 143-174.

P Erdos (1959) Graph Theory and Probability. 11, 34-38.

E El-Kholy, A Al-Esawy (2005) Graph folding of some special graphs. 1(1), 66-70.

E El-Kholy, A El-Esawy (2014) Graph Folding of Some Special Graphs. 1(1), 66-70.

Martin Golumbic (2004) Perfect graphs. 7, 51-80.

L Lovasz (1984) Normal Hypergraphs and the Weak Perfect Graph Conjecture. 21, 29-42.

W Lowell, J Robin (1983) Selected topics in graph theory2.