Geodesic
The Petersen and Heawood graphs make up graphical twins via induced matchings
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 677-683

Voir la notice de l'article provenant de la source Library of Science

Inspired by the Isaacs remark (published in 1975), we show that the Petersen and Heawood graphs (Pg and Hg) make up a bijectively linked pair of graphs. Another related new result is that Pg is uniquely decomposable into five induced 3-matchings. It shows a kind of the structural rigidity of Pg. Information on maximal matchings with sizes 3, 4 and 5 in Pg is recalled. Constructive proofs confirm that the strong chromatic index sq(Pg)=5 and sq(Hg)=7. The three numerical edge coloring partitions for Pg are also determined.
Keywords: Heawood graph, induced matchings, Petersen graph, strong chromatic index 
Skupień, Zdzisław. The Petersen and Heawood graphs make up graphical twins via induced matchings. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 3, pp. 677-683. http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a5/
@article{DMGT_2023_43_3_a5,
     author = {Skupie\'n, Zdzis{\l}aw},
     title = {The {Petersen} and {Heawood} graphs make up graphical twins via induced matchings},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {677--683},
     year = {2023},
     volume = {43},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a5/}
}
TY  - JOUR
AU  - Skupień, Zdzisław
TI  - The Petersen and Heawood graphs make up graphical twins via induced matchings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 677
EP  - 683
VL  - 43
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a5/
LA  - en
ID  - DMGT_2023_43_3_a5
ER  - 
%0 Journal Article
%A Skupień, Zdzisław
%T The Petersen and Heawood graphs make up graphical twins via induced matchings
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 677-683
%V 43
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_3_a5/
%G en
%F DMGT_2023_43_3_a5

[1] G.M. Adel'son-Vel'skiǐ and V.K. Titov, On edge 4-chromatic cubic graphs, in: Proc. Conf. held at Moscow Univ. in Jan. 27–29, 1971, Voprosy Kibernetiki (1973) 5–14, in Russian.

[2] J.-C. Bermond, J.M.S. Simões-Pereira and C.M. Zamfirescu, On non-Hamiltonian homogeneously traceable digraphs, Math. Japon. 24 (1979/80) 423–426.

[3] G. Chartrand, R.J. Gould and S.P. Kapoor, On homogeneously traceable nonhamiltonian graphs, in: Proc. 2nd Internat. Conf. on Combinat. Math., Ann. New York Acad. Sci. 319 (1979) 130–135. https://doi.org/10.1111/j.1749-6632.1979.tb32783.x

[4] R.J. Faudree, R.H. Schelp, A. Gyárfás and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205–211.

[5] R.J. Gould, Degree sets for homogeneously traceably non-Hamiltonian graphs, Colloq. Math. 45 (1981) 155–158. https://doi.org/10.4064/cm-45-1-155-158

[6] P.J. Heawood, Map-colour theorem, Quart. J. Math. Oxford Ser. 24 (1890) 332–338.

[7] D.A. Holton and J. Sheehan, The Petersen Graph (Cambridge Univ. Press, Cambridge, 1993). https://doi.org/10.1017/CBO9780511662058

[8] R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221–239. https://doi.org/10.1080/00029890.1975.11993805

[9] J. Petersen, Sur le théorème de Tait, L'intermédiaire des Mathématiciens 5 (1898) 225–227.

[10] Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs (1976), preprint.

[11] Z. Skupień, Degrees in homogeneously traceable graphs, Ann. Discrete Math. 8 (1980) 185–188. https://doi.org/10.1016/S0167-5060(08)70871-9

[12] Z. Skupień, Maximum degree among vertices of a non-Hamiltonian homogeneously traceable graph, in: Combinatorics and Graph Theory, S.B. Rao (Ed(s)), Lecture Notes in Math. 885 (1981) 496–500.

[13] Z. Skupień, On homogeneously traceable nonhamiltonian digraphs and oriented graphs, in: The Theory and Applications of Graphs, G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Lesniak-Foster and D.R. Lick (Ed(s)), (Wiley, New York 1981) 517–527.

[14] Z. Skupień, Homogeneously traceable and Hamiltonian connected graphs, Demonstr. Math. 17 (1984) 1051–1067. https://doi.org/10.1515/dema-1984-0424

[15] M.M. Sysło and Z. Skupień, Applied Graph Theory III} Euler and Hamilton graphs. Saleman problem, Math. Appl. (Warsaw) X (1977) 5–54, in Polish.

[16] T. Zamfirescu, Three small cubic graphs with interesting Hamiltonian properties, J. Graph Theory 4 (1980) 287–292. https://doi.org/10.1002/jgt.3190040306