zbMATH — the first resource for mathematics

Regular $$n$$-valent $$n$$-connected non-Hamiltonian non $$n$$-edge-colourable graphs. (English) Zbl 0237.05106
For all $$n\geq 3$$, except $$n=5,6,$$ or 7 regular $$n$$-valent non-Hamiltonian non $$n$$-edge-colourable graphs are constructed by replacing edges of Petersen’s graph by multiple edges, then replacing vertices with complete bipartite graphs. For $$n=5,6$$, or 7, the same procedure gives graphs that are regular $$n$$-valent, Hamiltonian, and non $$n$$-edge-colourable but not $$n$$-connected.
Reviewer: G. H. J. Meredith

MSC:
 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory 05C99 Graph theory
Full Text:
References:
 [1] {\scG. H. J. Meredith}, Some families of non-Hamiltonian graphs, Proc. 1972 Oxford Combinatorics Conf., (D. J. A. Welsh, Ed.), I. M. A., to appear. · Zbl 0237.05106 [2] Nash-Williams, C.St.J.A., Possible directions in graph theory, () · Zbl 0263.05101 [3] Vizing, V.G., On an estimate of the chromatic class of a p-graph, Disker. analiz., 3, 25-30, (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.