# Journal of Graph Theory

Journal of Graph Theory > 63 > 1 > 68 - 81

*G*is a triangulation of the torus and χ(

*G*)≠5, then there is a 3‐coloring of the edges of

*G*so that the edges bounding every face are assigned three different colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 68–81, 2010

Journal of Graph Theory > 63 > 1 > 82 - 92

*C*of a digraph

*D*is extendable if there exists a directed cycle

*C*′ in

*D*that contains all vertices of

*C*and an additional one. In 1989, Hendry defined a digraph

*D*to be cycle extendable if it contains a directed cycle and every non‐Hamiltonian directed cycle of

*D*is extendable. Furthermore,

*D*is fully cycle extendable if it is cycle extendable and every vertex of

*D*belongs to a directed...

Journal of Graph Theory > 63 > 1 > 1 - 16

*G*is a maximal induced complete bipartite subgraph of

*G*. Given a graph

*G*, the biclique matrix of

*G*is a {0,1,−1} matrix having one row for each biclique and one column for each vertex of

*G*, and such that a pair of 1, −1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar...

Journal of Graph Theory > 63 > 1 > 17 - 30

*G*be a graph and let

*S*⊂

*V*(

*G*). We say that

*S*is

*dominating*in

*G*if each vertex of

*G*is in

*S*or adjacent to a vertex in

*S*. We show that every triangulation on the torus and the Klein bottle with

*n*vertices has a dominating set of cardinality at most \documentclass{article}\usepackage{amssymb}\footskip=0pc\pagestyle{empty}\begin{document} \end{document}. Moreover, we show that the same...

Journal of Graph Theory > 63 > 1 > 31 - 67

Journal of Graph Theory > 63 > 2 > 93 - 105

*r*which imply the existence of a vertex

*x*contained in

*r*circuits which have pairwise only

*x*in common. In particular, we give some positive answers to a question of P. Seymour, whether an

*r*‐regular digraph has a vertex

*x*which is contained in

*r*circuits pairwise disjoint except for

*x*, and show that the answer, in general, is negative. © 2009...

Journal of Graph Theory > 63 > 2 > 106 - 113

*G*be a simple graph of order

*n*with Laplacian spectrum {λ

_{n}, λ

_{n−1}, …, λ

_{1}} where 0=λ

_{n}≤λ

_{n−1}≤⋅≤λ

_{1}. If there exists a graph whose Laplacian spectrum is

*S*={0, 1, …,

*n*−1}, then we say that

*S*is Laplacian realizable. In 6, Fallat et al. posed a conjecture that

*S*is not Laplacian realizable for any

*n*≥2 and showed that the conjecture holds for

*n*≤11,

*n*is prime, or

*n*=2, 3(mod4). In this article, we have...

Journal of Graph Theory > 63 > 2 > 129 - 145

*G*is a 3 ‐connected plane graph with

*n*vertices, then the number of colors in such a coloring does not exceed $\lfloor{{7n-8}\over {9}}\rfloor$. If

*G*is 4 ‐connected, then the number of colors is at most $\lfloor {{5n-6}\over {8}}\rfloor$, and for

*n*≡3(mod8), it...

Journal of Graph Theory > 63 > 2 > 114 - 128

*d*‐regular simple graph to admit a decomposition into paths of length

*d*for odd

*d*>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We...

Journal of Graph Theory > 63 > 2 > 146 - 163

*G*−

*v*, obtained from the graph

*G*by deleting the vertex

*v*and all edges incident to

*v*, is called a card of

*G*. The deck of G is the multiset of its unlabelled vertex‐deleted subgraphs. The number of common cards of

*G*and

*H*(or between

*G*and

*H*) is the cardinality of the multiset intersection of the decks of

*G*and

*H*. In this article, we present infinite families of pairs of...

Journal of Graph Theory > 63 > 2 > 164 - 178

*r*

_{f}(

*a*

_{1},

*a*

_{2}, …,

*a*

_{k}) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case

*k*=2. In this article, we answer an open problem by determining an explicit formula for the general case

*k*>2 by constructing an infinite family of circulant graphs...

Journal of Graph Theory > 63 > 3 > 179 - 184

_{1}(

*S*

_{p}) of the orientable surface

*S*

_{p}of genus

*p*is the maximum chromatic number of all graphs which can be drawn on the surface so that each edge is crossed by no more than one other edge. We show that if there exists a finite field of order 4

*m*+1,

*m*≥3, then 8

*m*+2≤χ

_{1}(

*S*${\text{\hspace{0.17em}}}_{\text{4}\text{m}{\text{\hspace{0.17em}}}^{\text{2}}\text{\u2212}\text{m}\text{+1}}$)≤8

*m*+3, where 8

*m*+3 is Ringel's upper bound on χ

_{1}(

*S*${\text{\hspace{0.17em}}}_{\text{4}\text{m}{\text{\hspace{0.17em}}}^{\text{2}}\text{\u2212}\text{m}\text{+1}}$). © 2009 Wiley Periodicals, Inc. J Graph Theory...

Journal of Graph Theory > 63 > 3 > 231 - 242

Journal of Graph Theory > 63 > 3 > 198 - 209

*G*derived from the nonexistence of homomorphisms from some path \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{P}\end{eqnarray*}\end{document} into some orientation \documentclass{article}\footskip=0pc\pagestyle{empty}\begin{document}\begin{eqnarray*}\vec{G}\end{eqnarray*}\end{document} of

*G*. The condition...

Journal of Graph Theory > 63 > 3 > 226 - 230

*acyclic*edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The

*acyclic chromatic index*of a graph is the minimum number

*k*such that there is an acyclic edge coloring using

*k*colors and is denoted by

*a*′(

*G*). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that

*a*′(

*G*)⩽Δ+2, where Δ=Δ(

*G*) denotes the maximum degree of the graph. Alon et...

Journal of Graph Theory > 63 > 3 > 243 - 257

*T*is called a card. A collection of cards is called a deck. We say that the tree

*T*has a deck

*D*if each card in

*D*can be obtained by deleting distinct vertices of

*T*. If

*T*is the only unlabeled tree that has the deck

*D*, we say that

*T*is 𝒯‐reconstructible from

*D*. We want to know how large of a deck

*D*is necessary...

Journal of Graph Theory > 63 > 3 > 210 - 225

*balanced*if the sizes of the sets in the bipartition differ by at most one. B. Bollobás and A. D. Scott, Random Struct Alg 21 (2002), 414–430 conjectured that if

*G*is a graph with minimum degree of at least 2 then

*V*(

*G*) admits a balanced bipartition

*V*

_{1},

*V*

_{2}such that for each

*i*,

*G*has at most |

*E*(

*G*)|/3 edges with both ends in

*V*

_{i}. The minimum degree...

Journal of Graph Theory > 63 > 3 > 185 - 191

*G*is

*rainbow edge‐connected*if any two vertices are connected by a path whose edges have distinct colors. The

*rainbow connection*of a connected graph

*G*, denoted by

*rc*(

*G*), is the smallest number of colors that are needed in order to make

*G*rainbow edge‐connected. We prove that if

*G*has

*n*vertices and minimum degree δ then

*rc*(

*G*)<

*20*

*n*/δ. This solves open problems from Y. Caro, A....

Journal of Graph Theory > 63 > 3 > 192 - 197

*v*of a graph

*G*, we denote by

*d*(

*v*) the

*degree*of

*v*. The

*local connectivity*κ(

*u, v*) of two vertices

*u*and

*v*in a graph

*G*is the maximum number of internally disjoint

*u*–

*v*paths in

*G*, and the

*connectivity*of

*G*is defined as κ(

*G*)=

*min*{κ(

*u, v*)|

*u, v*∈

*V*(

*G*)}. Clearly, κ(

*u, v*)⩽

*min*{

*d*(

*u*),

*d*(

*v*)} for all pairs

*u*and

*v*of vertices in

*G*. Let δ(

*G*) be the minimum degree of

*G*. We call a graph

*G*

*maximally connected*...

Journal of Graph Theory > 63 > 4 > 338 - 348

*k*‐tournament, on

*n*vertices, 2≤

*k*≤

*n*, is a pair

*T*=(

*V, E*), where the vertex set

*V*is a set of size

*n*and the edge set

*E*is the collection of all possible subsets of size

*k*of

*V*, called the edges, each taken in one of its

*k*! possible permutations. A

*k*‐tournament is pancyclic if there exists (directed) cycles of all possible lengths; it is vertex‐pancyclic if moreover the cycles...