# Scientific Journals and Yearbooks Published at SAS

## Article List

## Tatra Mountains Mathematical Publications

Volume 9, 1996, No. 3

Content:

- Erdős, P.
**Some of my favourite problems on cycles and colorings.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 7-9. - Borodin, O.
**More about the weight of edges in planar graph.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 11-14. - Schiermeyer, I.
**Fast exact colouring algorithms.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 15-30. - Broersma, H. - Ryjacek, Z. - Schiermeyer, I.
**Unifying results on Hamiltonian claw-free graphs.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 31-39. - Owens, P.
**Shortness exponents for some families of maximal planar graphs.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 41-50. - Klesc, M.
**The crossing number of $K**_{2,3}× P_{n}$ and $K_{2,3}× S_{n}$.*Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 51-56. - Balińska, K. - Quintas, L.
**Isomorphism classes of one edge transformed graphs.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 57-67. - Tuza, Z. - Voigt, M.
**On a conjecture of Erdős, Rubin and Taylor.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 69-82. - Broere, I. - Jonck, E. - Voigt, M.
**The induced path number of a complete multipartite graph.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 83-88. - Miller, M.
**Some open problems in optimal digraphs.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 89-96. - Böhme, T. - Harant, J. - Tkac, M.
**On the minimal number of separating 3-cycles in non-hamiltonian maximal planar graphs.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 97-102. - Voss, H.
**Problem.***Tatra Mountains Mathematical Publications*. Vol. 9, no. 3 (1996), p. 103-104.

Some of my favourite problems on cycles and colorings.Paul Erdős ^{1)}
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)}
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)}
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,398
^{N})$, $O(1,585^{n})$, $O(1,938^{n})$ or $O(2,155^{n})$ 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)}
This work was motivated by many (recent) papers on hamiltonicity of claw-free graphs, i.e., graphs that do not contain $K
_{1,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)}
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 $K_{2,3}× P_{n}$ and $K_{2,3}× S_{n}$.Marian Klesc ^{1)}
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 $K
_{2,3}× P_{n}$ and $K_{2,3}× S_{n}$ where $P_{n}$ and $S_{n}$ are the path and the star with $n$ edges, respectively.How to cite (APA format): Klesc, M. (1996). The crossing number of $K_{2,3}× P_{n}$ and $K_{2,3}× S_{n}$. Tatra Mountains Mathematical Publications, 9(3), 51-56. | ||||||||

Isomorphism classes of one edge transformed graphs.Krystyna T. Balińska ^{1)}, Louis V. Quintas ^{2)}
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)}
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)}
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)}
The Moore bound for a digraph of maximum out-degree $d$ and diameter $k$ is $M
_{d, k}=1+d+…+d^{k}$. It is known that digraphs of order $M_{d, 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)=M_{d, k}-Δ_{d, 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)}
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)}
How to cite (APA format): Voss, H. (1996). Problem. Tatra Mountains Mathematical Publications, 9(3), 103-104. |