Two n-edge colorings of a graph are edge-Kempe equivalent if one can be obtained from the other by a series of edge-Kempe switches. In this work we show every planar bipartite cubic graph has exactly ...one edge-Kempe equivalence class, when 3=χ′(G) colors are used. In contrast, we also exhibit infinite families of nonplanar bipartite cubic (and thus 3-edge colorable) graphs with a range of numbers of edge-Kempe equivalence classes when using 3 colors. These results address a question raised by Mohar.
For a graph G and a set H of connected graphs, G is said to be H-free if G does not contain any member of H as an induced subgraph. We let G2(H) denote the set of all 2-connected H-free graphs. ...Fujisawa et al. (2013) characterized sets H of connected graphs such that |H|≤3 and G2(H) is finite. In this paper, we extend their result and characterize sets H of connected graphs such that |H|≤4 and G2(H) is finite.
A k-walk of a graph is a spanning closed walk meeting each vertex at most k times. In this paper, we consider sets of forbidden subgraphs that imply the existence of a k-walk in a connected graph of ...sufficiently large order, and give a characterization of such sets for k=2.
We improve upon the best known upper and lower bounds on the sizes of minimal feedback vertex sets in butterflies. Also, we construct new feedback vertex sets in grids so that for a large number of ...pairs
(
n
,
m
)
, the size of our feedback vertex set in the grid
M
n
,
m
matches the best known lower bound, and for all other pairs it differs from this lower bound by at most 2.
The looseness
ξ
(
G
)
of a triangulation
G on a closed surface
F
2
is defined as the minimum number
k such that for any surjection
c
:
V
(
G
)
→
{
1
,
2
,
…
,
3
+
k
}
, there exists a face
uvw
of
G ...which gets three distinct colors
c
(
u
)
,
c
(
v
)
and
c
(
w
)
. We define
ξ
min
(
G
)
and
ξ
max
(
G
)
as the minimum and the maximum of
ξ
(
G
′
)
taken over all triangulations
G
′
on
F
2
isomorphic to
G as graphs. We shall show that
ξ
max
(
G
)
-
ξ
min
(
G
)
⩽
2
⌊
(
2
-
χ
(
F
2
)
)
/
2
⌋
, where
χ
(
F
2
)
stands for the Euler characteristic
χ
(
F
2
)
, and in particular that two triangulations on the projective plane have the same looseness if they are isomorphic as graphs.
We study the stability of some classes of graphs defined in terms of forbidden subgraphs under the closure operation introduced by the second author. Using these results, we prove that every ...2-connected claw-free and
P
7-free, or claw-free and
Z
4-free, or claw-free and eiffel-free graph is either hamiltonian or belongs to a certain class of exceptions (all of them having connectivity 2).
PDF