# Scientific Journals and Yearbooks Published at SAS

## Tatra Mountains Mathematical Publications

Volume 9, 1996, No. 3

Content:

Some of my favourite problems on cycles and colorings.

Paul Erdős 1)

 1) Mathematical Institute, Hungarian Academy of Sciences; Realtanoda u. 13-15; H-1053 Budapest; HUNGARY.

Six problems concerning graph cycles and colourings are presented.

How to cite (APA format):
Erdős, P. (1996). Some of my favourite problems on cycles and colorings. Tatra Mountains Mathematical Publications, 9(3), 7-9.

More about the weight of edges in planar graph.

Oleg Borodin 1)

 1) Institute of Mathematics, Siberian Branch of Russian Academy of Sciences; Novosibirsk, 630090; RUSSIA.

The weight of an edge in a plane graph is the degree sum of its end vertices. Recent results on the minimum weight of all edges, denoted by $w$, of those incident with a triangle, $w*$, and those incident with two triangles, $w*\ast$, in a plane graph are discussed. It is proved that if a normal plane map has $w*\ast=∞$, then either $w*≤ 9$ or $w≤ 8$, where both bounds are sharp.

How to cite (APA format):
Borodin, O. (1996). More about the weight of edges in planar graph. Tatra Mountains Mathematical Publications, 9(3), 11-14.

Fast exact colouring algorithms.

Ingo Schiermeyer 1)

 1) RWTH Aachen, Department C of Mathematics; Templergraben 55; D-52056 Aachen; GERMANY.

In this paper we describe and analyze four improved algorithms for deciding the $3-, 4-, 5-$ and $6-$ Colourability problem. If $G$ is a simple graph on $n$ vertices then we will show that these algorithms test a graph for $3-, 4-, 5-$ or $6$-Colourability, i.e., an assignment of three, four, five or six colours to the vertices of $G$ such that two adjacent vertices obtain different colours, in less than $O(1,398N)$, $O(1,585n)$, $O(1,938n)$ or $O(2,155n)$ steps.

How to cite (APA format):
Schiermeyer, I. (1996). Fast exact colouring algorithms. Tatra Mountains Mathematical Publications, 9(3), 15-30.

Unifying results on Hamiltonian claw-free graphs.

Hajo J. Broersma 1), Zdeněk Ryjacek 2), Ingo Schiermeyer 3)

 1) Faculty of Mathematical Sciences, University of Twente; P.O.Box 217; 7500 AE Enschede; NETHERLAND. 2) Katedra matematiky, Zapadoceska univerzita; Univerzitni 22; 306 14 Plzen; CZ. 3) RWTH Aachen, Department C of Mathematics; Templergraben 55; D-52056 Aachen; GERMANY.

This work was motivated by many (recent) papers on hamiltonicity of claw-free graphs, i.e., graphs that do not contain $K1,3$ as an induced subgraph. By combining ideas from these papers with some new observations, we unify several of the existing sufficiency results, using a new sufficient condition consisting of seven subconditions. If each pair of vertices at distance two of a 2-connected claw-free graph $G$ satisfies at least one of these subconditions, then $G$ is Hamiltonian. We also present infinite classes of examples of graphs showing that these subconditions are, in some sense, independent.

How to cite (APA format):
Broersma, H, Ryjacek, Z, Schiermeyer, I. (1996). Unifying results on Hamiltonian claw-free graphs. Tatra Mountains Mathematical Publications, 9(3), 31-39.

Shortness exponents for some families of maximal planar graphs.

Peter John Owens 1)

 1) Department of Mathematics and Statistics, University of Surrey; Guildford GU2 5XH; U. K..

It is shown that the family of maximal planar simple graphs such that every vertex has valency 5 or $q≥ 14$, not only has non-Hamiltonian members but even has a shortness exponent less than one.

How to cite (APA format):
Owens, P. (1996). Shortness exponents for some families of maximal planar graphs. Tatra Mountains Mathematical Publications, 9(3), 41-50.

The crossing number of $K2,3× Pn$ and $K2,3× Sn$.

Marian Klesc 1)

 1) Katedra matematiky FEI TU, Hlavna 6, 042 00 Kosice, Slovakia. marian.klesc@tuke.sk

There are several known exact results on the crossing number of Cartesian product of paths or cycles with small'' graphs. Here we determine the crossing number of $K2,3× Pn$ and $K2,3× Sn$ where $Pn$ and $Sn$ are the path and the star with $n$ edges, respectively.

How to cite (APA format):
Klesc, M. (1996). The crossing number of $K2,3× Pn$ and $K2,3× Sn$. Tatra Mountains Mathematical Publications, 9(3), 51-56.

Isomorphism classes of one edge transformed graphs.

Krystyna T. Balińska 1), Louis V. Quintas 2)

 1) Computer Science Center, Technical University of Poznań; Pl. M. Sklodowskej-Curie 5; 60-965 Poznań; POLAND. 2) Mathematics Department, Pace University; New York, NY 10038; U. S. A..

The isomorphism classes and the chromatic numbers of the one edge deleted subgraphs and the one edge extended supergraphs of a graph are studied. Graphs are determined having the property that either every one edge deleted subgraph or every one edge extended supergraph is isomorphically distinct. The following is one of a number of open problems considered. For a given chromatic number $χ0$, characterize the class of graphs $\langle G\rangle$ such that $χ(G)=χ0$ and every one edge extended supergraph of $G$ has chromatic number $χ0$. Similarly, characterize the class of graphs $\langle H\rangle$ such that $χ(H)=χ0$ and every one edge extended supergraph of $H$ has chromatic number $χ0+1$.

How to cite (APA format):
Balińska, K, Quintas, L. (1996). Isomorphism classes of one edge transformed graphs. Tatra Mountains Mathematical Publications, 9(3), 57-67.

On a conjecture of Erdős, Rubin and Taylor.

Zsolt Tuza 1), Margit Voigt 2)

 1) Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17; H-1111 Budapest; HUNGARY. tuza@lutra.sztaki.hu 2) Institut für Mathematik, Technische Universitat Ilmenau; D-98684 Ilmenau; GERMANY.

A graph $G$ with vertex set $V$ and edge set $E$ is called $(a, b)$-choosable if for any assignment of lists $L(v)$ of colours to the vertices $v$ of $G$ with $|L(v)|=a$ it is possible to choose subsets $C(v)\subset L(v)$, $|C(v)|=b$ for every $v\in V$ such that $C(u)\cap C(v)=\emptyset$ for all $uv\in E$. In 1979, Erdős, Rubin and Taylor [P. Erdős, A. L. Rubin, H. Taylor: Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics Graph Theory and Computing, Arcata, California, 1979, Congressus Numeratium 26 (1979), 125–157] raised the conjecture that every $(a, b)$-choosable graph $G$ is also $(am, bm)$-choosable for all $m>1$. We investigate the case $b=1$, presenting some classes of $(a, 1)$-choosable graphs for which $(am,m)$-choosability can be proved for all $m$.

How to cite (APA format):
Tuza, Z, Voigt, M. (1996). On a conjecture of Erdős, Rubin and Taylor. Tatra Mountains Mathematical Publications, 9(3), 69-82.

The induced path number of a complete multipartite graph.

Izak Broere 1), Elizabeth Jonck 2), Margit Voigt 3)

 1) Department of Mathematics, Rand Afrikaans University; P.O.Box 524; Auckland Paark; 2006 SOUTH AFRICA. 2) Department of Mathematics, Rand Afrikaans University; P. O. Box 524; Auckland Park; 2006 SOUTH AFRICA. 3) Institut für Mathematik, Technische Universitat Ilmenau; D-98684 Ilmenau; GERMANY.

The induced path number $ρ(G)$ of a graph $G$ is defined as the minimum number of subsets into which the vertex set of $G$ can be partitioned so that each subset induces a path. In this paper we determine the induced path number of a complete $l$-partite graph.

How to cite (APA format):
Broere, I, Jonck, E, Voigt, M. (1996). The induced path number of a complete multipartite graph. Tatra Mountains Mathematical Publications, 9(3), 83-88.

Some open problems in optimal digraphs.

Mirka Miller 1)

 1) Department of Computer Science, The University of Newcastle; NSW 2308 AUSTRALIA.

The Moore bound for a digraph of maximum out-degree $d$ and diameter $k$ is $Md, k=1+d+…+dk$. It is known that digraphs of order $Md, k$ do not exist for $d>1$ and $k>1$. This being the case, for $d>1$ and $k>1$, we consider digraphs which are close' to Moore, that is, digraphs with maximum out-degree $d≥ 2$, diameter $k≥ 2$ and order $n(d, k)=Md, kd, k$ where $Δd, k$ is the minimum possible defect' for given $d$ and $k$. Furthermore, we consider the construction of diregular digraphs with minimum diameter, given the order and degree. At the end of each section we present a number of open problems.

How to cite (APA format):
Miller, M. (1996). Some open problems in optimal digraphs. Tatra Mountains Mathematical Publications, 9(3), 89-96.

On the minimal number of separating 3-cycles in non-hamiltonian maximal planar graphs.

Thomas Böhme 1), Jochen Harant 2), Michal Tkac 3)

 1) Institut Für Mathematik, TU Ilmenau; PF 327,G-98684 Ilmenau; Germany. 2) Institute of Mathematics, Technical University Ilmenau; Postfach 327; D-98684 Ilmenau; GERMANY. 3) Strojnicka fakulta TU, Letna 9; 040 00 Kosice.

A well known theorem of H. Whitney states that every maximal planar graph without separating 3-cycles is Hamiltonian. The problem discussed here is how many separating 3-cycles such a graph must have to be non-Hamiltonian.

How to cite (APA format):
Böhme, T, Harant, J, Tkac, M. (1996). On the minimal number of separating 3-cycles in non-hamiltonian maximal planar graphs. Tatra Mountains Mathematical Publications, 9(3), 97-102.

Problem.

Heinz-Jürgen Voss 1)

 1) Technische Universitat Dresden, Abteilung Mathematik; Institut für Algebra; Mommsenstrasse 13; 01062 Dresden; GERMANY.

How to cite (APA format):
Voss, H. (1996). Problem. Tatra Mountains Mathematical Publications, 9(3), 103-104.