# Multi-step planning with learned effects of partial action executions

Hakan Aktasa, Utku Bozdogana and Emre Ugura CONTACT Hakan Aktas Email:
<EMAIL_ADDRESS>aDepartment of Computer Engineering, Bogazici
University, Istanbul, Turkiye

###### Abstract

In this paper, we propose a novel affordance model, which combines object,
action, and effect information in the latent space of a predictive neural
network architecture that is built on Conditional Neural Processes. Our model
allows us to make predictions of intermediate effects expected to be obtained
during action executions and make multi-step plans that include partial
actions. We first compared the prediction capability of our model using an
existing interaction data set and showed that it outperforms a recurrent
neural network-based model in predicting the effects of lever-up actions.
Next, we showed that our model can generate accurate effect predictions for
other actions, such as push and grasp actions. Our system was shown to
generate successful multi-step plans to bring objects to desired positions
using the traditional A* search algorithm. Furthermore, we realized a
continuous planning method and showed that the proposed system generated more
accurate and effective plans with sequences of partial action executions
compared to plans that only consider full action executions using both
planning algorithms.

###### keywords:

Affordances, effect prediction, object motion trajectory prediction, multi-
step planning

††articletype: FULL PAPER

##  1 Introduction

From a robotics standpoint, learning to predict the effects of a robot’s
actions beforehand would be a beneficial skill for robots, since this can
prevent potential failures and dangerous situations for the robot and those
around it, and enable planning for achieving certain goals. Planning for
multi-step tasks in the real world is difficult, and a generalized approach to
solving this problem is even more so. Due to its difficulty, previous works
compromise on certain aspects, such as predefining effect categories or object
categories, simplifying the task. Discretizing information in the continuous
sensorimotor space with the purpose of high-level symbolic planning with
symbols may result in inaccurate plans.The current study is different from the
previous studies in the sense that the previous studies only considered the
final effect (and final effect category, and for this, they need to make
clustering in effect space), whereas our study utilizes effect prediction
trajectory along the action execution. Our study can sample any point along
the predicted effect trajectory and use the predicted effect in planning.
Additionally, a new motion planning algorithm is proposed as a continuous
solution.

In robotics, learned affordances have been used to choose objects for
manipulation, to make discrete and continuous effect predictions given objects
and actions, and to make plans to achieve goals [1, 2, 3, 4]. However, to the
best of our knowledge, there is no single framework that can achieve all the
following,

  * •

predict the effects given objects and action

  * •

predict required actions to achieve desired goals

  * •

predict the movement trajectory of the objects in response to parametric
actions

  * •

make plans composed of a sequence of actions, including partial action
executions, in order to achieve given goals

The contribution of our work is as follows:

  * •

A novel latent representation for affordances: Considering affordances as
relations between objects, actions, and effects, our neural network-based
architecture forms a representation that encodes object, continuous action,
and continuous effect information in a single latent layer.

  * •

Accurate continuous effect prediction: Our system can predict the motion
trajectories of the objects expected to be generated by parametric robot
actions. We showed that the high prediction performance compared to a strong
baseline also makes affordance-based continuous effect prediction.

  * •

Multi-step planning with partial actions: We exploited the outcome prediction
capability of our system for partial actions in order to form multi-step plans
that may include full or partial action executions. To show this, we both used
a traditional planning method namely A* and we also proposed a new continuous
adaptive planning algorithm that better utilizes our method.

##  2 Related work

#### Early affordances work on effect predictions

In early works such as [5], objects were required to be recognized first, and
object-specific affordances were learned from the robot’s interaction
experience with those objects, therefore the learned affordances could not be
generalized to different/novel objects. [6] studies learning of traversability
affordance where the LIDAR input was directly processed without any object
detection step. Therefore, the ‘direct perception’ aspect of affordance
perception was realized in that work, however only a single pre-defined
affordance category was addressed. Effect categories and affordances were
discovered by the robot in [7] via unsupervised clustering techniques.
However, unsupervised clustering results depend on the particular clustering
method and the feature space that might be composed of values with different
metrics such as distance, frequency, angle, etc. In [8], this is taken one
step further and hierarchical clustering is made over channels for better
effect category discovery. Both [7] and [8] also enable forward chaining for
multi-step planning. Bayesian Networks were used [9, 10], enabling
bidirectional predictive capabilities using the robot’s own interaction
experience, but clustering is performed on object features and effects in a
predefined manner. In this paper, we also study acquiring bi-directional
prediction capabilities. Different from previous work, we do not find effect
clusters or do not only aim to predict the final effect. Instead, our system
aims to learn how to predict the complete effect/action trajectory during
action execution.

#### Learning affordances for planning

[11] learned affordances for symbolic planning, by again clustering effect
categories and using object categories as a collection of effect categories
obtainable by actions available to the robot. This enables the representation
of nonlinear relations in planning, however, their discrete representation
while making planning easy, makes the estimations approximate, increasing
long-horizon planning errors. This work was validated on a real-world setup
with simple actions such as poke, grasp, and release, and also with a more
complex action which is stack. The experience of the robot enabled it to gain
experience from the simple actions and after experiencing the stack action
enabled it to generate a valid plan for the stacking action. This framework
was extended in [12] by enabling the robot to progressively update the
previously learned concepts and rules in order to better deal with novel
situations that appear during multi-step action executions. Similar planning
capabilities were obtained by the robot using deep encoder-decoder neural
networks with binary bottleneck layers [13] and with multi-head attention
mechanism [14] by directly processing the pixel images instead of using hand-
coded features. In [15], probabilistic planning with symbols using
parameterized actions was applied to a real robot task, showing that
continuous tasks can be performed with discrete planners using parameterized
behaviors. Different from the previous work where only final outcomes were
used for planning, our system can exploit intermediate effects expected to be
observed for example in the middle of the action execution for planning.

#### Learning visual grasp affordances

Using RGB/RGBD images for predicting affordance classes or pixel-wise
affordance labels for object manipulation has become popular in recent years
[16, 17, 18, 19, 20, 21] and was shown to be a feasible approach for learning
how to grasp different objects. Similarly, [22] are able to learn the
affordances of objects such that they can place objects/humans in correct
poses in a scene and also choose the correct object type to place in a given
scene. [23] and [24] extracted not only object features but also the visual
features of tools from their images to generate motion trajectories using
tools as a part of affordance.[25] uses point clouds to learn general
geometric features from object interactions, enabling them to place objects in
a scene correctly. In [26], a generative model learned from interaction images
was used to propose potential affordances. The aim was to learn a
generalizable prior from interaction data and then utilize it to propose
reasonable goals for unseen objects. These goals were then attempted to be
executed by an offline RL policy, learned from interaction data, and tuned
online efficiently to adapt to unseen objects. However, continuous effect
prediction and multi-step planning aspects were not addressed in these
studies.

#### Affordances for efficient learning

Affordances can also be used to reduce the search space in order to
efficiently generate plans to solve long-horizon tasks. Recent approaches
utilizing this idea extended the definition of affordances to represent not
only single-step action-effect knowledge but as action feasibilities [27], or
intents that are similar to goals [28] in order to make affordances useful for
multi-step plans. However, the feasibility concept of [27] accepts a grasp
action achieving nothing as afforded, and would also accept a grasp action as
afforded regardless of whether it was an appropriate grasp for an object.
While [28] overcame this with intent representation, intents were specified a
priori in their work and although a sub-goal discovery direction was proposed
for learning, it was not explored.

#### Learning continuous effect trajectories

Similar to our work, [29] and [30] learned to predict the full motion
trajectory of an object, using the robot’s own interaction experience, and
top-down images of the objects. These studies are important for their
inclusion of the temporal aspect of effects. The utility of different features
was also investigated, such as hand-crafted shape features, CNN-extracted
features, or support point features extracted from a neural network. The
authors used these features and the interaction experience to train recurrent
neural networks and were able to accurately predict trajectories resulting
from a lever-up action in a real-world setting with multiple objects. A common
shortcoming of the aforementioned methods which make predictions for action or
effects is related to the use of recurrent methods for long-horizon tasks. The
use of recurrent networks such as LSTMs [31] or GRUs [32] is shown to be
effective for short-term predictions. In this paper, we compare the effect
prediction capabilities of recurrent neural network-based systems and our
conditional neural process-based system.

##  3 Proposed Method

###  3.1 General Architecture

We propose a framework that can learn (i) predicting the effect trajectory
given the initial object image and action execution trajectory, and (ii)
finding the required action execution trajectory to achieve a desired effect
on a given object. Our system is built on top of Conditional Neural Processes
(CNPs) [33] that bring together the inference potential of Gaussian Processes
and the training of neural networks with gradient descent by learning a prior
from data. As we would like to predict both actions and effects from objects
and (possibly missing) actions and effects, we propose a neural network
structure that takes the object image as input together with action and/or
effect values at different time points. In other words, given the initial
object image, our network can be conditioned with action and/or effect values
at different time points in order to generate action and effect values for all
time points during action execution. The general structure of the proposed
system is shown in Fig. 1. As shown the system is composed of two encoders
that process action and effect information at different time points, an image
encoder that processes the depth image of the object, averaging operations to
acquire a common object-action-effect representation (r), which in turn can be
used to predict action and effect values at other time points using the
corresponding two decoders.

Figure 1: An overview of the proposed model. Given object image and action or
effect information at any time-point, our system can generate the effect
trajectory and action execution trajectory.

In detail, inspired by Deep Modality Blending Networks [34], our system
encodes information coming from different channels (object, action, and
effect) into a common latent space, using a weighted average of encoded
modality representations, facilitating information sharing, and also providing
a regularization effect on the representations learned, similar to dropout
[35].

In our implementation, the system is object-centric. An action is defined in
terms of the distance of the robot’s end-effector to the object’s initial
position and also the orientation of the gripper along with a binary value
that shows whether the gripper is open or not. An effect is defined as the
displacement and the change in orientation of the object from its starting
position throughout an action. A depth image of the object is included as an
external parameter $\gamma$ for the action. $a_{t}$ and $e_{t}$, represent the
action and the effect at time $t$ respectively and since the object is
independent of the $t$, it is represented by $o$ and is equal among the
interaction trajectory $D_{d}$.

$D_{d}=(\\{a_{t},e_{t},o,t\\}_{t=0}^{t=1})_{d}$ (1)

is an interaction trajectory where $1\leq d\leq m$ and $m$ is the number of
trajectories in the data set $D$. $0\leq t\leq 1$ is a phase variable in
control of the passage of time where $t\in\mathbf{R}$. Observation points
sampled from these interaction trajectories are used as input to the
corresponding channels of the model. Each channel is encoded separately by its
own encoder and the latent representations are subjected to a weighted
averaging operation:

$r_{i}=\sum h_{a}(a_{t_{obs_{i}}})*w_{1}+h_{e}(e_{t_{obs{i}}})*w_{2}$ (2)

where $w_{1}+w_{2}=1$, $h_{a}$ and $h_{e}$ represents action encoder and
effect encoder respectively, and $a_{t_{obs_{i}}}$ and $e_{t_{obs_{i}}}$
represent the action and the effect observation points sampled from
observation trajectory $i$. Each latent representation constructed by encoders
is represented by $r_{i}$ and at each iteration $k$ latent representations are
constructed. $k$ is selected randomly at each iteration. The $r_{i}$ values
obtained from these calculations are then averaged:

$r=r_{1}\oplus r_{2}\oplus r_{3}\oplus...\oplus r_{k}$ (3)

where the commutative operation used is averaging. Then, depth image features
and target time-step are concatenated to form the merged representation
$r_{mrg}=\\{r,f(\gamma_{o}),t_{target}\\}$ where $f(\gamma_{o})$ represents
the latent representation obtained by passing the object’s depth image through
the image encoder and $t_{target}$ represents the queried time (shown as
$t_{q}$ in the Figure 1).

This merged representation is then decoded by separate decoders, each
corresponding to a different channel. This merged representation is decoded at
the action decoder ($g_{a}$) by

$g_{a}(r_{mrg})=(\mu_{a_{t_{target}}},\sigma_{a_{t_{target}}}),$ (4)

and the effect decoder ($g_{e}$) by

$g_{e}(r_{mrg})=(\mu_{e_{t_{target}}},\sigma_{e_{t_{target}}}),$ (5)

to yield predictions for action and/or effect for the target time step shown
in Fig 1. Here, mean values are used as predictions, and variances are only
used to calculate the loss of the system and can also be used to determine how
confident the system is with the current predicted value.

The latent representation (r) can be viewed as the shared affordance
representation for actions $a$ and effects $e$ for different objects $o$.
Learned affordances can then be used to predict the effects of actions or the
required action to generate target effects. This model can be used to create
multi-step action plans to achieve goals beyond single-action executions by
chaining the predictions.

###  3.2 Training

At each training iteration, $k$ observations are sampled uniformly at random
from a randomly selected interaction trajectory $D_{d}$ where $1\leq k\leq
obs_{max}$, $k\in\mathbf{N}$ is also a uniform random number, and $obs_{max}$
is a hyper-parameter denoting the maximum number of observations the model is
allowed to use during one iteration. These observations are then encoded and
aggregated. A cropped object depth image is encoded separately on a CNN
encoder network, and the resulting vector is concatenated at the end of this
aggregated representation. Before a prediction can be made, a target time step
is also concatenated to the image features. Finally, this merged
representation is decoded to yield predictions for action and/or effect for
the target time step shown in Fig 1. Gradient descent is used with the loss
function (6) with Adam optimizer [36].

$\mathcal{L}(\theta,\delta)=-logP(y_{j}|\mu_{j},softmax(\sigma_{j}))$ (6)

After training, the network is able to predict the entire interaction
trajectory given any novel point(s) on a trajectory. An A* planner [37] is
then used on top of the network to solve tasks requiring multiple actions and
steps.

Figure 2: Scene showing the parameters of a push action around an object.

###  3.3 Actions

Our arm-hand robot is equipped with three actions, namely push, grasp, and
rotate. The parametric push action is specified by an angle
$\theta\in[0,2\pi]$; a push distance $l=0.05$ and a $radius=0.2$ both in
meters. The gripper starts the push execution from the red circumference of a
circle of radius ($radius=20cm$) centered around the object (see Figure 2), at
an angle $\theta$ and pushes the object $l$ meters from its center of mass.

Larger-sized objects may be displaced more as a result of this setup. The
model is expected to learn the rollability and pushability affordances from
these interactions and based on the object shape be able to predict the
trajectories of rollable objects such as spheres or lying cylinders and non-
rollable objects such as cuboids or upright cylinders.Since the rollable
objects are unstable if the push actions used for non-rollable objects are
used for the rollable ones, the objects keep moving even after the action is
completed which makes it impossible to make multiple step plans using these
objects. To overcome this challenge we devised a new action that keeps the
rollable objects from rolling off after the action is completed. Using this
action, our model can make different plans for objects with different
behaviors to achieve the same goal which is to take the object to the desired
object location. This action is executed by lowering the open gripper on top
of the object, closing it to keep the object in place, and then taking it to
the desired location. Although this action is a little different than a usual
push action, we will call it push for simplicity. The difference between the
action for a not rollable and a rollable object can be seen in Figure 3.

Grasp actions, on the other hand, are realized by lowering the open gripper to
grasp position, and attempting to grasp an object by closing the gripper and
lifting the gripper up. Our model is expected to learn the graspability
affordance from these interactions. Based on object size and shape, it should
also be able to predict the interaction trajectories. Rotate actions are
similar, and realized by lowering the open gripper on top of the object,
closing the gripper to keep it in place, and rotating the gripper to rotate
the object.

Figure 3: The actions used to push a non-rollable object (cylinder in the
figure) and a rollable object (sphere in the figure). All push actions used to
train the network are composed of two steps as shown: approach the object and
bring it to the desired location. The desired location is shown with the green
shaded area. Based on the angle to push the orientation of the gripper
changes. Note that, the sphere is not elevated during this action.

###  3.4 Planning with partial action executions

For the planning with partial action executions, we experimented using two
approaches. We used A* planning algorithm to show that our model can be used
with traditional planning methods. We also proposed a proprietary planning
algorithm that utilizes the full potential of our method, and compared its
results with the A*.

The A* planner (with Euclidean distance to the goal heuristic) is used to
generate a sequence of actions to move the object from its initial position to
a goal position. Each branch in the search tree corresponds to either a push
action or a grasp action. As grasp and rotate actions are not parameterized,
there are single branches for grasp and rotate actions. On the other hand, as
a push action might be applied from different approach angles and for
different push distances, the range of possible approach angles and push
distances are discretized and used to create multiple branches from the same
node in the search tree. The initial 20%, 40%, 60%, 80%, and 100% segments of
push action were considered during the search. Additionally, the push
direction was discretized into 36 directions. Therefore, the branching factor
was set to 180.

The planner uses predictions of actions with different parameters to update
the predicted location of the object. The actions are assumed to be known and
the effects of those actions are generated by the proposed deep neural network
model. To generate a sequence of actions, the effect predictions that are
generated using the segmented actions are traversed in the search tree to find
a sequence with a desirable outcome. The search is completed if the difference
between the predicted and goal object position is less than 2 cm. Our model is
able to work with continuous inputs, however, the planner can only propose a
finite amount of actions due to the mentioned discretization design choice.

Interactions with single and multiple actions are generated, which also
include partial actions. Partial actions are when an action is started to be
applied. However, it is not completed, i.e. it is executed partially. For
example in a push action, the push may be cut short before the gripper even
contacts the object, or the gripper reaches the center of mass of the object,
meaning that the object has already started being pushed, but the push is not
completed yet. Importantly, our model is trained only with full-action
interactions. Yet, our model can generate the effect at any desired time
point, and therefore it can predict the consequence of partial action
executions. The planner can use the effects of such partial action executions
to generate plans with finer resolutions (compared to plans that can only
include full action executions).

We also propose a continuous method for motion planning to take full advantage
of our model’s capabilities. In our method, we realize the push actions in two
steps. First, the direction to the desired location is found, and then the
object is pushed to the desired location either partially or fully. To find
the direction in which the object needs to be pushed, we uniformly sample a
random point along the circumference of the circle the push actions are
defined on (section 3.3). Then this point is given as input to the effect
channel of our model. The input for the action channel can be set to any value
since we set the weight of the action channel to zero and the weight of the
effect channel to one during this process. Assuming the time is normalized, we
set $t_{target}=1$ since the points along the circumference of the circle
correspond to the last points of the trajectories that lead to that point.
After providing the object depth image as input to the model, we obtain a
prediction in the output of the effect decoder which is close to the point we
set as input to the effect encoder.

Our aim is to make this predicted point as close to the desired location as
possible since the closest point to the desired location will be along the
direction to the desired object location. To this end, we calculate the mean
squared error between the predicted point and the desired final object
location. Using the value obtained from this calculation as the loss, we apply
gradient descent to the input of the effect encoder to adjust the input until
we get the input that produces the closest point to the desired location. Note
that the rest of the model is not trained during these calculations. Gradient
descent is only applied to the input of the effect encoder to adjust it, not
to train any part of the model. Using this, our system is able to find the
direction to the desired object location after sufficient iterations are
carried out. This way the direction of the action is found in a continuous
manner.

After finding the direction, the system is queried using $t_{target}$ values
between $0$ and $1$ until the desired object location is achieved. If the
desired location is in between the initial position and the range of the full
push action, the system is queried until the predicted object location is not
getting closer to the desired location and thus a partial action is found. If
the desired location is on the end of the action range or beyond it (another
action is needed), then the system is queried until $t_{target}=1$ . This way,
any segment of any action that starts from the starting point of the action
can be used as a partial action trajectory during execution. If more than one
action is needed, the predicted object position at $t_{target}=1$ is used as
the object starting point of the next action in the action sequence. This
process is repeated before execution until the desired object location is
reached.

Using this method, the sequence of actions needed to bring the object to the
desired location in the 2D plane is determined before the execution starts.
After each execution, the algorithm also checks whether the object is in the
planned location and whether any goal change has occurred to adapt to any
unexpected changes. After each execution, if the object is not in the expected
location or the goal has changed in between executions, a new plan is made to
bring the object to the desired location, and the initial plan is discarded.
If the object used has different rollability affordance characteristics
depending on which of its faces it is standing on (like the cylinder), and if
the object falls over during action execution (its rollability affordance is
changed), the planner revises the plan and makes a plan that is suited for the
other affordance characteristic of the object by using the new top-down depth
image of the object. The grasp and rotate actions can be chained to the end of
the planning in the xy plane if the object is wanted to be in a certain height
or orientation. The desired height or rotation can be achieved by querying
until the desired height or rotation is obtained using the grasp and the
rotate actions respectively.

Note that an action can be applied only if the object is reachable by the
robot. Our model is expected to learn the reachability affordance from
interactions experiences and actions are only considered during planning if
the object is reachable.

##  4 Experiments results

###  4.1 Effect prediction performance

(a)

(b)

Figure 4: (a) A sample random shape (pentagon) and the corresponding object.
(b) A number of randomly generated sample shapes. Reused with permission from
[29].

In this paper, we propose a novel system to predict the effects given objects
and actions. Furthermore, our system can generate complete motion trajectories
of objects as effects rather than their final positions. In order to assess
the performance of our system, we compare our system with a recent study that
can also predict motion trajectories of objects using CNN and Long short Term
Memory (LSTM) model [29]. We used the same dataset that [29] used where lever-
up actions were applied to objects with different geometric shapes from
different points. An example lever-up action is shown in Figure 5. The objects
had different number of edges (between 3 and 8), sizes, and orientations. Some
examples of the objects used in this experiment can be seen in Figure 4. The
objects were levered up from different contact points. The authors translated
and rotated the top-down 128x128 grayscale image according to the contact
point and lever-up direction in order to simplify the prediction problem. The
dataset was separated randomly into 80% training, 10% validation, and 10%
testing as in [29].

Figure 5: Example lever-up action in the simulator, reused with permission
from [29].

The experiments were performed with 5-fold cross-validation and early stopping
with one million iterations. For comparison, we gathered n-step predictions,
taking 15 previous steps as observations, and compared the results with the
ones reported in the same manner in [29]. As shown in Table 4.1, the error
between the predicted and actual positions of the objects in [29] varies
between $0.90-1.00$cm, whereas the error was in the range of $0.3-0.4$cm in
our system. The total movement of the objects used is around 10 centimeters.
This comparison shows our model yields significantly lower error rates
compared to a recurrent method since the output is predicted directly avoiding
error accumulation for multi-step predictions.

N-step prediction errors obtained in our model and the LSTM model.  N-step Our
Model LSTM Model 1-step (cm) $0.340\pm 0.044$ $1.02\pm 0.01$ 2-step (cm)
$0.352\pm 0.046$ $1.00\pm 0.02$ 3-step (cm) $0.364\pm 0.049$ $0.96\pm 0.03$
4-step (cm) $0.375\pm 0.051$ $1.01\pm 0.04$ 5-step (cm) $0.387\pm 0.054$
$0.91\pm 0.03$

###  4.2 Training Environment

A simulated scene was constructed in CoppeliaSim [38] as shown in Figure 2. A
UR10 robot interacts with objects of different shapes and sizes by applying
push and grasp actions on a tabletop setting. A Kinect sensor is placed above
the table vertically such that the entire table is visible. The parts of the
interaction where the object is potentially going to be displaced are
recorded. The recorded information consists of action and effect data from
once every 3 simulation steps (a single step is 50ms), which is chosen
empirically, and a single depth image of the table with the object on top
taken at the beginning of each interaction. The simulation dataset is split
into training (%80), validation (%10) and test (%10) sets.

###  4.3 Single-action push and grasp effect prediction

Different models were trained for push and grasp actions separately. The
simulation data sets were always split between 80% training, 10% validation,
and 10% test data. For all the results reported in this work, 10-fold cross-
validation was applied unless otherwise specified. The models were trained for
one million iterations, without batches due to variable length of inputs, and
early stopping was employed. The learning rate was set to $1\mathrm{e}{-4}$.
All errors reported in meters denote the distances to a specified goal
position. The predictions for a single action are fixed to take 25 time steps.

For the push action, a data set made up of 500 trajectories was used. For each
interaction, objects were chosen randomly and placed at the center of the
table. An angle for the push $\theta\in[0,2\pi]$ was chosen randomly. The
robot performed a complete push action and the resulting interaction data was
recorded. The error in predicting the final position of the object was found
to be around $0.02$m as shown in Table 4.4. Similar to our analysis in the
previous subsection, our system was shown to be effective in predicting object
motion trajectories in push-like actions.

For the grasp action, a data set made up of 100 trajectories was used. Objects
of varying sizes were randomly chosen to be placed at the center of the table.
The robot then performed the grasp action and the resulting interaction data
was recorded. The results for the grasp action are provided in Table 4.3. In
interpreting the performance and success of graspability prediction, if the
change in height is larger than 0.1 meters, the grasp was assumed to be a
success. If the change in height is less than 0.1 meters, it is a failed
grasp. If the test data does not have a significant change in its z-axis
coordinates but the predictions do, then this is a false positive and finally,
if the test data has a significant change in z-axis coordinates but the
predictions do not, then it is a false negative. We have found that the robot
had more difficulty grasping rollable objects of equal size, most likely due
to the fact that a cube and an upright cylinder are both grasped by straight
surfaces whereas large spheres and sideways cylinders are grasped by curved
surfaces from points that are located above their center of mass, causing them
to slip easier. This difference can be seen in Table 4.3

Single grasp action prediction results on variable-sized objects of different
rollability placed on a fixed location.  Object Type Error (m) True True False
False Positive (%) Negative (%) Positive (%) Negative (%) Rollable $0.277\pm
0.0086$ 71.72 89.52 10.48 28.28 Non-rollable $0.273\pm 0.0067$ 79.62 91.43
8.57 21.38

As shown, our system could successfully predict graspability affordance.
However, it is important to note that the average grasp action error is
significantly larger than the average push action error. The mean error was
relatively high because the incorrect graspability predictions generated high
positional errors that significantly increased the mean error value. This is
potentially due to unsuccessful grasps. In the event of an unsuccessful grasp,
the object may slowly slip from the robot’s hands and land on the table close
to its initial position. The object may topple or roll (sometimes off the
table), leading to position changes that are uncertain beforehand and
therefore cannot be accurately predicted.

###  4.4 Planning performance

Next, our model is requested to generate plans to bring the object to goal
positions that might be beyond the range of single pushes or closer than a
full push. Therefore, the planner is expected to generate sequences of actions
that might include partial executions as well. A sample plan execution is
shown in Figure 6, where the plan is composed of two actions. The goal is
shown with a blue box, the actual object positions are shown with red color,
and the predictions are shown with green color.

Figure 6: Results of applying the model’s predicted actions in a scene. Images
are ordered from left to right. The top row is from the first action
execution, the bottom row is from the second action execution. The blue object
denotes the target position, the red object is generated from the robot’s
effect predictions. The blue and red objects are not interactable by the
robot. The green object is interactable and is acted upon by the robot, to
show the ground truth results of the robot’s predicted actions.

Given goal positions, we run our model in three modes:

  * •

predict one push action to reach a goal, which is maximum one step ahead,

  * •

predict one (possibly partial) push action to reach a goal, which is maximum
one step ahead,

  * •

predict the sequence of (possibly partial) push actions to reach a goal, which
is maximum three steps ahead.

For this part, we experimented with both our model and the LSTM model.
However, since the LSTM model does not perform well in long-horizon
prediction, in most of our trials, the actions produced by the LSTM model were
mostly unusable. During execution, the objects mostly either fell over, slid
off the gripper’s fingers, or in some cases fell off the table which made the
positional error results we obtained unusable for comparison. Because of this,
we decided to focus on comparing the planning algorithms instead. In order to
compare their performance we ran a number of trials for these three modes
using both our proposed planning method and A* planner. After plans are made,
they are executed by the robot. The distance between the goal position and the
final actual position of the object is reported as an error. The results are
provided in Table 4.4. For the A* planner, the object can be brought to the
goal position more accurately if the partial actions are considered during
planning even in a single-action execution case. Even error obtained in
multiple (potentially partial) action executions is smaller than single full
action execution. This shows the effectiveness of our system in making
accurate plans. Across the modes, our proposed method performed better than A*
planner with a significant decrease in displacement error. It can also be seen
that the error values obtained using our method are very close for all modes.
Since our method can use any segment of the given action primitives for
planning, the sampling frequency of the trajectories affects the precision of
our system significantly. This effect can be seen in Table 4.4. By increasing
the sampling frequency, we sampled the same push action paths to trajectories
with sample sizes 100 and 300, and this increase in sample size decreased the
positional error of the trials significantly. We did not observe any notable
difference between the accuracy of plans made for rollable or non-rollable
objects. Unexpected changes during execution like changing the goal position
or objects falling over also did not cause any difference in positional error
values. For the results reported in Table 4.4; the single full setting is
tested with 50 goals, the single partial setting with 100 goals, and the multi
partial setting with 80 goals.

The comparison of A* planner and our method for the three experiment modes.
The effect of the sampling frequency on our method can be seen from the
difference between the mean values of the third and the fourth column.  N-step
A* Planner Our Method size=100 Our Method size=300 Single Full (m) $0.020\pm
0.002$ $0.0074\pm 0.0017$ $0.0021\pm 0.00044$ Single Partial (m) $0.013\pm
0.002$ $0.0077\pm 0.0016$ $0.0022\pm 0.00068$ Multi Partial (m) $0.013\pm
0.002$ $0.0077\pm 0.0013$ $0.0022\pm 0.00046$

##  5 Conclusion

In this paper, we realized a model for multi-step action and effect
prediction. While previous work’s utilization of bidirectional learning is
limited, our model specifically creates its latent representations using this
concept and is able to make multi-step predictions that are in accordance with
ground truth manipulations. We emphasize using object-centric inputs to
achieve generalizability and investigate simple affordances of several classes
of objects of different sizes. By using a network for single interaction
predictions which can be interpreted similarly to a state transition function
and pairing it with a planner with heuristics to propose goal-directed actions
the model was shown to achieve low error in reaching target positions. While
the results of our experiments are promising, the model still requires
verification in the real world. Our next step is gathering data and testing
our implementation with a real robot.

Our work uses a conditional architecture to avoid the compounding error
problems of recurrent architectures and models that are used in a similar way
by feeding their current step output as the next step input. This advantage of
using conditional models is shown in this work against using an LSTM network,
and against a Multimodal Variational Autoencoder (MVAE) in [34]. Recently,
transformer models gained popularity as being a good alternative to recurrent
models. By using the attention mechanism they eliminate the need for
recurrence, and attention can potentially be beneficial for our model as well.
We plan to investigate the capabilities of such models in the future.

##  6 Disclosure statement

No potential conflict of interest was reported by the authors.

## Acknowledgement(s)

The numerical calculations reported in this paper were partially performed at
TUBITAK ULAKBIM, High Performance and Grid Computing Center (TRUBA resources).
The authors would like to thank Alper Ahmetoglu for providing insightful
comments for this paper.

## Funding

This research was supported by TUBITAK (The Scientific and Technological
Research Council of Turkey) ARDEB; 1001 program (project number: 120E274);
TUBITAK BIDEB; 2210-A program; and by the BAGEP Award of the Science Academy.

## References

  * [1] Jamone L, Ugur E, Cangelosi A, et al. Affordances in psychology, neuroscience, and robotics: A survey. IEEE Transactions on Cognitive and Developmental Systems. 2016;10(1):4–25.
  * [2] Yamanobe N, Wan W, Ramirez-Alpizar IG, et al. A brief review of affordance in robotic manipulation research. Advanced Robotics. 2017;31(19-20):1086–1101.
  * [3] Zech P, Haller S, Lakani SR, et al. Computational models of affordance in robotics: a taxonomy and systematic classification. Adaptive Behavior. 2017;25(5):235–271.
  * [4] Taniguchi T, Ugur E, Hoffmann M, et al. Symbol emergence in cognitive developmental systems: a survey. IEEE transactions on Cognitive and Developmental Systems. 2018;11(4):494–516.
  * [5] Fitzpatrick P, Metta G, Natale L, et al. Learning about objects through action-initial steps towards artificial cognition. In: 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422); Vol. 3; IEEE; 2003. p. 3140–3145.
  * [6] Ugur E, Dogar MR, Cakmak M, et al. The learning and use of traversability affordance using range images on a mobile robot. In: Proceedings 2007 IEEE International Conference on Robotics and Automation; IEEE; 2007. p. 1721–1726.
  * [7] Ugur E, Oztop E, Şahin E. Going beyond the perception of affordances: Learning how to actualize them through behavioral parameters. In: 2011 IEEE International Conference on Robotics and Automation; IEEE; 2011. p. 4768–4773.
  * [8] Ugur E, Oztop E, Sahin E. Goal emulation and planning in perceptual space using learned affordances. Robotics and Autonomous Systems. 2011;59(7-8):580–595.
  * [9] Montesano L, Lopes M, Bernardino A, et al. Modeling affordances using bayesian networks. In: 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems; IEEE; 2007. p. 4102–4107.
  * [10] Montesano L, Lopes M, Bernardino A, et al. Learning object affordances: from sensory–motor coordination to imitation. IEEE Transactions on Robotics. 2008;24(1):15–26.
  * [11] Ugur E, Piater J. Bottom-up learning of object categories, action effects and logical rules: From continuous manipulative exploration to symbolic planning. In: 2015 IEEE International Conference on Robotics and Automation (ICRA); IEEE; 2015. p. 2627–2633.
  * [12] Ugur E, Piater J. Refining discovered symbols with multi-step interaction experience. In: 2015 IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids); IEEE; 2015. p. 1007–1012.
  * [13] Ahmetoglu A, Seker MY, Piater J, et al. Deepsym: Deep symbol generation and rule learning for planning from unsupervised robot interaction. Journal of Artificial Intelligence Research. 2022;75:709–745.
  * [14] Ahmetoglu A, Oztop E, Ugur E. Learning multi-object symbols for manipulation with attentive deep effect predictors. arXiv preprint arXiv:220801021. 2022;.
  * [15] Ames B, Thackston A, Konidaris G. Learning symbolic representations for planning with parameterized skills. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS); IEEE; 2018. p. 526–533.
  * [16] Nguyen A, Kanoulas D, Caldwell DG, et al. Detecting object affordances with convolutional neural networks. In: 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS); IEEE; 2016. p. 2765–2770.
  * [17] Do TT, Nguyen A, Reid I. Affordancenet: An end-to-end deep learning approach for object affordance detection. In: 2018 IEEE international conference on robotics and automation (ICRA); IEEE; 2018. p. 5882–5889.
  * [18] Mi J, Tang S, Deng Z, et al. Object affordance based multimodal fusion for natural human-robot interaction. Cognitive Systems Research. 2019;54:128–137.
  * [19] Hämäläinen A, Arndt K, Ghadirzadeh A, et al. Affordance learning for end-to-end visuomotor robot control. In: 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS); IEEE; 2019. p. 1781–1788.
  * [20] Chu FJ, Xu R, Seguin L, et al. Toward affordance detection and ranking on novel objects for real-world robotic manipulation. IEEE Robotics and Automation Letters. 2019;4(4):4070–4077.
  * [21] Thermos S, Potamianos G, Daras P. Joint object affordance reasoning and segmentation in rgb-d videos. IEEE Access. 2021;9:89699–89713.
  * [22] Zhang L, Du W, Zhou S, et al. Inpaint2learn: A self-supervised framework for affordance learning. In: Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision; 2022. p. 2665–2674.
  * [23] Saito N, Ogata T, Mori H, et al. Tool-use model to reproduce the goal situations considering relationship among tools, objects, actions and effects using multimodal deep neural networks. Frontiers in Robotics and AI. 2021;:309.
  * [24] Mar T, Tikhanoff V, Natale L. What can i do with this tool? self-supervised learning of tool affordances from their 3-d geometry. IEEE Transactions on Cognitive and Developmental Systems. 2017;10(3):595–610.
  * [25] Ruiz E, Mayol-Cuevas W. Geometric affordance perception: Leveraging deep 3d saliency with the interaction tensor. Frontiers in Neurorobotics. 2020;14:45.
  * [26] Khazatsky A, Nair A, Jing D, et al. What can i do here? learning new skills by imagining visual affordances. In: 2021 IEEE International Conference on Robotics and Automation (ICRA); IEEE; 2021. p. 14291–14297.
  * [27] Xu D, Mandlekar A, Martín-Martín R, et al. Deep affordance foresight: Planning through what can be done in the future. arXiv preprint arXiv:201108424. 2020;.
  * [28] Khetarpal K, Ahmed Z, Comanici G, et al. What can i do here? a theory of affordances in reinforcement learning. In: International Conference on Machine Learning; PMLR; 2020. p. 5243–5253.
  * [29] Seker MY, Tekden AE, Ugur E. Deep effect trajectory prediction in robot manipulation. Robotics and Autonomous Systems. 2019;119:173–184.
  * [30] Tekden AE, Erdem A, Erdem E, et al. Belief regulated dual propagation nets for learning action effects on groups of articulated objects. In: 2020 IEEE International Conference on Robotics and Automation (ICRA); IEEE; 2020. p. 10556–10562.
  * [31] Hochreiter S, Schmidhuber J. Long short-term memory. Neural computation. 1997;9(8):1735–1780.
  * [32] Cho K, Van Merriënboer B, Gulcehre C, et al. Learning phrase representations using rnn encoder-decoder for statistical machine translation. arXiv preprint arXiv:14061078. 2014;.
  * [33] Garnelo M, Rosenbaum D, Maddison CJ, et al. Conditional neural processes. arXiv preprint arXiv:180701613. 2018;.
  * [34] Seker MY, Ahmetoglu A, Nagai Y, et al. Imitation and mirror systems in robots through deep modality blending networks. Neural Networks. 2022;146:22–35.
  * [35] Srivastava N, Hinton G, Krizhevsky A, et al. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research. 2014;15(1):1929–1958.
  * [36] Kingma DP, Ba J. Adam: A method for stochastic optimization. arXiv preprint arXiv:14126980. 2014;.
  * [37] Hart P, Nilsson N, Raphael B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics. 1968;4(2):100–107. Available from: https://doi.org/10.1109/tssc.1968.300136.
  * [38] Rohmer E, Singh SPN, Freese M. Coppeliasim (formerly v-rep): a versatile and scalable robot simulation framework. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS); Tokyo, Japan; 2013.

## Appendix

Image Encoder  Layer Input Size Output Size Conv3×3 + LeakyReLU + MaxPool2×2
(48, 48, 2) (24, 24, 32) Conv3×3 + LeakyReLU + MaxPool2×2 (24, 24, 32) (12,
12, 64) Conv3×3 + LeakyReLU + MaxPool2×2 (12, 12, 64) (6, 6, 64) Conv3×3 +
LeakyReLU + MaxPool2×2 (6, 6, 64) (3, 3, 128) Conv3×3 + LeakyReLU + MaxPool2×2
(3, 3, 128) (1, 1, 128) Flatten (1, 1, 128) 128 Dense 128 16

Action Encoder  Layer Input Size Output Size Dense + LeakyReLU 3 32 Dense +
LeakyReLU 32 64 Dense + LeakyReLU 64 64 Dense + LeakyReLU 64 128 Dense +
LeakyReLU 128 128 Dense + LeakyReLU 128 256 Dense + LeakyReLU 256 128

Effect Encoder  Layer Input Size Output Size Dense + LeakyReLU 3 32 Dense +
LeakyReLU 32 64 Dense + LeakyReLU 64 64 Dense + LeakyReLU 64 128 Dense +
LeakyReLU 128 128 Dense + LeakyReLU 128 256 Dense 256 128

Action Decoder  Layer Input Size Output Size Dense + LeakyReLU 1024 512 Dense
+ LeakyReLU 512 256 Dense + LeakyReLU 256 128 Dense + LeakyReLU 128 32 Dense +
LeakyReLU 32 4

Effect Decoder  Layer Input Size Output Size Dense + LeakyReLU 1024 512 Dense
+ LeakyReLU 512 256 Dense + LeakyReLU 256 128 Dense + LeakyReLU 128 32 Dense +
LeakyReLU 32 4

Overall structure of the model  Layer Input Size Output Size Object Encoder
(48, 48, 2) 16 Action Encoder 3 128 Effect Encoder 3 128 Concatanate - Action
+ Object + $t_{q}$ 128 + 16 + 1 145 Concatanate - Effect + Object + $t_{q}$
128 + 16 + 1 145 1D Avarage - Effect + Action 145 + 145 145 Dense 145 1024
Action Decoder 1024 4 Effect Decoder 1024 4

Algorithm 1 Proposed Planning Algorithm (without online checking)

$actionSequence\leftarrow[\;]$

$successValue\leftarrow$ $\triangleright$ Can be set to any success distance

while Object is not in the desired position do

$direction\leftarrow sampleRandomPointOnCircle()$

while $direction$ changes do $\triangleright$ won’t change after solution’s
been found

$predictedAction,predictedEffect\leftarrow model.predict([t=1,direction])$

$loss\leftarrow meanSquaredError(targetPosition,predictedEffect)$

$gradient\leftarrow calculateGradient(direction,loss)$

$applyGradient(gradient,direction)$

end while

$fullActionTraj,fullEffectTraj\leftarrow model.predict([t,direction]),0\leq
t\leq 1$

$index\leftarrow 0$

$done\leftarrow false$

while $index<size(fullEffectTraj)$ do

if $successValue>distanceBetween(target,fullEffectTraj[index])$ then

$actionSequence.append(fullActionTraj[0:index])$

$done\leftarrow true$

$break$

end if

end while

if $done=false$ then

$actionSequence.append(fullActionTraj)$

end if

if $done=true$ then

$break$

end if

end while


# On the $\Delta$-edge stability number of graphs

Saieed Akbaria Email<EMAIL_ADDRESS>Reza Hosseini Dolatabadib Email:
<EMAIL_ADDRESS>Mohsen Jamaalia Email<EMAIL_ADDRESS>Sandi
Klavžar e,f,g Email<EMAIL_ADDRESS>Nazanin Movarraeic Email:
<EMAIL_ADDRESS>
###### Abstract

The $\Delta$-edge stability number ${\rm es}_{\Delta}(G)$ of a graph $G$ is
the minimum number of edges of $G$ whose removal results in a subgraph $H$
with $\Delta(H)=\Delta(G)-1$. Sets whose removal results in a subgraph with
smaller maximum degree are called mitigating sets. It is proved that there
always exists a mitigating set which induces a disjoint union of paths of
order $2$ or $3$. Minimum mitigating sets which induce matchings are
characterized. It is proved that to obtain an upper bound of the form ${\rm
es}_{\Delta}(G)\leq c|V(G)|$ for an arbitrary graph $G$ of given maximum
degree $\Delta$, where $c$ is a given constant, it suffices to prove the bound
for $\Delta$-regular graphs. Sharp upper bounds of this form are derived for
regular graphs. It is proved that if $\Delta(G)\geq\frac{|V(G)|-2}{3}$ or the
induced subgraph on maximum degree vertices has a $\Delta(G)$-edge coloring,
then ${\rm es}_{\Delta}(G)\leq|V(G)|/2$.

a Department of Mathematical Sciences, Sharif University of Technology

b Department of Computer Engineering, Sharif University of Technology

c School of Mathematics, Institute for Research in Fundamental Sciences

e Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

f Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

g Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

Keywords: vertex degree; $\Delta$-edge stability number; matching; edge
coloring

AMS Subj. Class. (2020): 05C75, 05C07, 05C70, 05C15

##  1 Introduction

Let $G$ be a graph and let $\Delta(G)$ denote its maximum degree. The
$\Delta$-edge stability number, $\operatorname{{\rm es}_{\Delta}}(G)$, of $G$,
is the minimum number of edges of $G$ in which their deletions result in a
subgraph $H$ with $\Delta(H)=\Delta(G)-1$. This graph invariant has been for
the first time investigated by Borg and Fenech in [7]. The vertex version of
the problem, that is, the $\Delta$-vertex stability number, has been studied
in [5, 6]. Furthermore, over the last few years, the corresponding problems
for the chromatic number and the chromatic index were respectively
investigated in [3, 8] and [1, 2, 15, 16, 17].

The above discussion naturally fall within the following broader framework
recently proposed in [13] and further elaborated in [4, 14]. For an arbitrary
graph invariant $\tau$, the $\tau$-vertex stability number (the $\tau$-edge
stability number) is the minimum number of vertices (edges) whose removal
results in a subgraph $H$ with $\tau(H)\neq\tau(G)$. The corresponding minimum
number of vertices and edges are respectively denoted by ${\rm vs}_{\tau}(G)$
and ${\rm es}_{\tau}(G)$. Following this general framework we use in this
paper the notation $\operatorname{{\rm es}_{\Delta}}(G)$, although we should
add that the $\Delta$-edge stability number and the $\Delta$-vertex stability
number of a graph $G$ were in [7, 6] respectively denoted by $\lambda_{\rm
e}(G)$ and $\lambda(G)$.

In the seminal paper [7] the focus was on the upper bounds of the
$\Delta$-edge stability number in terms of the size of the graph, the maximum
degree, and the number of vertices of maximum degree. In this paper, we
continue with the exploration of the $\Delta$-edge stability number. Our main
goal is to find tight bounds for $\operatorname{{\rm es}_{\Delta}}(G)$ based
on the order of the graph.

The paper is organized as follows. In the rest of the introduction, we briefly
define notations used in the paper and recall a result to be used later on. In
the subsequent section, we prove several general properties for sets of edges
whose removal decreases the maximum degree. In particular, we prove that there
always exists such a set which induces a disjoint union of paths of order $2$
or $3$, and characterize smallest such sets which are matchings. In Section 3
we prove that to obtain an upper bound of the form $\operatorname{{\rm
es}_{\Delta}}(G)\leq c|V(G)|$ for an arbitrary graph $G$ of given maximum
degree $\Delta$, where $c$ is a given constant, it sufficed to prove the bound
for $\Delta$-regular graphs. In Section 4 sharp upper bound for regular graphs
are derived. In the final section, we prove that the $\Delta$-edge stability
number is bounded from the above by one-half of the order for each graph in
which vertices of maximum degree induce a Class 1 graph, as well as for graphs
$G$ with $\Delta(G)\geq\frac{|V(G)|-2}{3}$.

Throughout this paper all graphs are finite and simple, that is, with no loops
and multiple edges, and moreover, with at least one edge. Let $G=(V(G),E(G))$
be a graph. The degree of a vertex $u$ of $G$ is denoted by $d_{G}(u)$.
Further, $\delta(G)$ is the minimum degree of $G$. The subgraph of $G$ induced
by a set $A$ of vertices and/or edges will be denoted by $G\left[A\right]$.
The number of edges between two disjoint sets of vertices $S,T\subseteq V(G)$
is denoted by $e(S,T)$. The open neighborhood $N_{G}(v)$ of a vertex $v\in
V(G)$ is the set of neighbors of $v$, the closed neighborhood of $v$ is
$N_{G}[v]=N_{G}(v)\cup\\{v\\}$. If $S\subseteq V(G)$, then the open and the
closed neighborhood of $S$ are the respective sets $N_{G}(S)=\cup_{v\in
S}N_{G}(v)$ and $N_{G}[S]=\cup_{v\in S}N_{G}[v]$. If the graph $G$ is clear
from the context, we may omit the subscript $G$ in the above notation. The
independence number of $G$ is denoted by $\alpha(G)$ and its matching number
by $\alpha^{\prime}(G)$. The odd girth of $G$ is the length of a shortest odd
cycle in $G$ and is denoted by ${\rm og}(G)$.

The core of $G$ is the set of vertices of $G$ of maximum degree and is denoted
by $\operatorname{\rm Core}(G)$. Clearly, if $G$ is regular, then
$\operatorname{\rm Core}(G)=V(G)$. If $S\subseteq E(G)$ is such that
$\Delta(G-S)=\Delta(G)-1$, then we say that $S$ is a mitigating set of $G$. In
that case, we also say that $G[S]$ is a mitigating subgraph of $G$.

Given a graph $G$, a function $c:E(G)\to\\{c_{1},\ldots,c_{k}\\}$ with
$c(e)\neq c(f)$ for any two adjacent edges $e$ and $f$ is a _proper $k$-edge
coloring_ of $G$. The minimum $k$ for which $G$ admits a proper $k$-edge
coloring is the _chromatic index_ of $G$, and denoted by $\chi^{\prime}(G)$.
We let $[k]=\\{1,\ldots,k\\}$. For any $i\in[\chi^{\prime}(G)]$, let $C_{i}$
denote the set of all edges of $G$ that are colored by $c_{i}$ in the proper
edge coloring $c$. For any $v\in V(G)$, let $c(v)$ denote the set of colors
appearing in $v$. Vizing’s Theorem [19] states that the chromatic index of an
arbitrary simple graph lies between the maximum degree $\Delta(G)$ and
$\Delta(G)+1$. Graphs with $\chi^{\prime}(G)=\Delta(G)$ are said to be Class
$1$, while graphs with $\chi^{\prime}(G)=\Delta(G)+1$ are said to be Class
$2$.

Throughout the following we will use Tutte’s Theorem, which states that a
graph has a perfect matching if and only if $o(G-S)\leq|S|$ for every
$S\subseteq V(G)$, where $o(H)$ denotes the number of odd components of a
graph $H$. We conclude the preliminaries by recalling the following result to
be used later on.

######  Theorem 1.1.

[7, Theorem 2.8] If $G$ is a graph, then $\operatorname{{\rm
es}_{\Delta}}(G)=|\operatorname{\rm
Core}(G)|-\alpha^{\prime}(G[\operatorname{\rm Core}(G)])$.

##  2 Properties of mitigating sets

In this section, we first prove that one can always find a mitigating subgraph
of $G$ whose each component is $P_{2}$ or $P_{3}$, and give an upper bound on
the $\Delta$-edge stability number involving the independence number. To
derive both results, Hall’s Theorem will be applied. Afterwards, we
characterize in two ways minimum mitigating sets which are matchings.

######  Theorem 2.1.

If $G$ is a graph of order $n$, then the following properties hold.

  1. (i)

There exists a mitigating subgraph of $G$ whose each component is $P_{2}$ or
$P_{3}$.

  2. (ii)

$\operatorname{{\rm es}_{\Delta}}(G)\leq n-\alpha(G)$, and the bound is sharp.

###### Proof.

(i) Let $M$ be a maximum matching of $G[\operatorname{\rm Core}(G)]$, and let
$A\subseteq\operatorname{\rm Core}(G)$ be the set of vertices of
$\operatorname{\rm Core}(G)$ which are not saturated by $M$. As $M$ is a
maximum matching of $G[\operatorname{\rm Core}(G)]$, the set $A$ is
independent. Furthermore, since the vertices in $A$ are of maximum degree,
$|N(A^{\prime})|\geq|A^{\prime}|$ holds for each $A^{\prime}\subseteq A$.
Therefore, by Hall’s Theorem, there exists a matching $M^{\prime}$ in $G$ that
saturates $A$. By applying Theorem 1.1 we have

$\displaystyle\operatorname{{\rm es}_{\Delta}}(G)$ $\displaystyle\leq|M\cup
M^{\prime}|\leq|M|+|M^{\prime}|$
$\displaystyle=\alpha^{\prime}(G[\operatorname{\rm
Core}(G)])+(|\operatorname{\rm Core}(G)|-2\alpha^{\prime}(][\operatorname{\rm
Core}(G)]))$ $\displaystyle=|\operatorname{\rm
Core}(G)|-\alpha^{\prime}(G[\operatorname{\rm Core}(G)])$
$\displaystyle=\operatorname{{\rm es}_{\Delta}}(G)\,,$

hence equality must hold in the first line. Therefore, $M\cup M^{\prime}$ is a
mitigating set of $G$.

Since $M$ is a maximum matching of $G[\operatorname{\rm Core}(G)]$, there is
no pair of edges of $M^{\prime}$ which meet an edge of $M$. Thus, any
component of $M\cup M^{\prime}$ is $P_{2}$ or $P_{3}$.

(ii) Let $I\subseteq V\left(G\right)$ be an independent set of size
$\alpha(G)$, and $A=\operatorname{\rm Core}(G)\cap I$. By Hall’s Theorem,
there exists a matching $M$ in $G$ that saturates $A$. Assume $B\subseteq
V(G)\setminus I$ is the set of vertices of $V(G)\setminus A$ which are
saturated by $M$. Let $S$ be the set of edges containing $M$ as well as one
edge adjacent to each vertex of $V(G)\setminus(I\cup B)$. Clearly, $G\setminus
S$ has no vertex of degree $\Delta$. Since

$|S|=|M|+(n-|I\cup B|)=|M|+n-(\alpha(G)+|M|)=n-\alpha(G)\,,$

the bound is proved. To see that it is sharp, consider an arbitrary regular,
bipartite graph $G$ with a perfect matching. Then $\operatorname{{\rm
es}_{\Delta}}(G)=\alpha(G)=n/2$. ∎

To characterize minimum mitigating sets, we need a lemma which can be deduced
from Tutte’s Theorem.

######  Lemma 2.2.

Let $G$ be a graph and $A\subseteq V(G)$. If for all $S\subseteq V(G)$ we have

$o_{G[A]}(G\setminus S)\leq|S|,$

then there exists a matching in $G$ that saturates $A$, where
$o_{G[A]}(G\setminus S)$ is the number of odd components of $G\setminus S$
which are contained in $A$.

###### Proof.

Let $n=|V(G)|$ and $B=G\setminus A$. Let $H$ be the graph obtained by the
disjoint union of $K_{n}$ and $G$ and joining each vertex of $K_{n}$ to any
vertex of $B$. Clearly, $H$ is of order $2n$. Moreover, as the order of $H$ is
even, we see that $H$ has a perfect matching if and only if $G$ has a matching
that saturates $A$. Note that maybe some edges in the matching have one
endpoint in $A$ and another in $B$. Assume for the contrary that no matching
in $G$ covers $A$. Therefore, by Tutte’s Theorem there exists $S\subseteq
V(H)$ such that

$o(H\setminus S)\geq|S|+2\,.$ (1)

If $V(K_{n})\subseteq S$, then $|S|\geq\frac{|V(H)|}{2}$ and thus, (1) does
not hold. Hence there exists $v\in V(K_{n})\setminus S$. Obviously, there are
at least $|S|+1$ odd components of $H\setminus S$ that are contained in $A$,
which is a contradiction, and the lemma is proved. ∎

We now characterize minimum mitigating sets which are matchings as follows.

######  Theorem 2.3.

If $G$ is a graph, and $S\subseteq V(G)$, then the following statements are
equivalent:

  1. (1)

$G$ has a matching that saturates $\operatorname{\rm Core}(G)$.

  2. (2)

$G$ has a minimum mitigating set which is a matching.

  3. (3)

For every $S\subseteq\operatorname{\rm Core}(G)$, $\operatorname{{\rm
es}_{\Delta}}(G[N[S]])\leq\frac{|V(G[N[S]])|}{2}$.

###### Proof.

We first show that (1) and (2) are equivalent. It is clear that if there is a
minimum mitigating set which is a matching, this matching saturates
$\operatorname{\rm Core}(G)$. For the reverse, suppose $M$ is a matching that
saturates $\operatorname{\rm Core}(G)$ and let $L$ be a minimum mitigating set
for $G$. We claim that $L$ could be chosen as a matching using induction on
$\operatorname{{\rm es}_{\Delta}}(G)$. If $\operatorname{{\rm
es}_{\Delta}}(G)=1$, the claim is obvious. Hence, assume that
$\operatorname{{\rm es}_{\Delta}}(G)\geq 2$. Clearly, $|M|\geq|L|$. If
$L\setminus M=\varnothing$, $L$ must be a matching and the claim is proved.
Thus, assume $e\in L\setminus M$. Since $|L|\geq 2$, we have
$\Delta(G\setminus e)=\Delta(G)$. Therefore, $M$ is a matching that saturates
$\operatorname{\rm Core}(G\setminus e)$. By the induction hypothesis, there
exists a minimum mitigating set for $G\setminus e$, say $L^{\prime}$, which is
a matching and $|L^{\prime}|=\operatorname{{\rm es}_{\Delta}}(G)-1$.
Obviously, $L^{\prime\prime}=L^{\prime}\cup\\{e\\}$ is a minimum mitigating
set for $G$. If $e$ is not adjacent to any edge in $L^{\prime}$, the claim is
proved. Since $L^{\prime}$ is matching and $L^{\prime\prime}$ is a minimum
mitigating set, $e$ is adjacent to at most one edge in $L^{\prime}$, say
$e^{\prime}$. Let $e=uv$ and $e^{\prime}=vw$ for some $u,v,w\in V(G)$. It is
easy to see that $d(u)=\Delta$. Since $uv\notin M$, there exists
$e_{1}=uy_{1}\in M$. Replace $e$ with $e_{1}$ in $L^{\prime\prime}$ and the
resulting mitigating set is still minimum and is a matching, unless there
exists $e^{\prime}_{1}=y_{1}x_{1}\in L^{\prime\prime}$ and $d(x_{1})=\Delta$.
Otherwise, if we remove $e^{\prime}_{1}$ from $L^{\prime\prime}$, the
resulting set of edges is still a mitigating set. Replace $e^{\prime}_{1}$
with some $e_{2}=x_{1}y_{2}\in M$ to obtain a new minimum mitigating set and
continue this operation and in each step replace $e^{\prime}_{i}$ with
$e_{i+1}$. Note that if $d(x_{i})<\Delta$ or there is no edge in $L^{\prime}$
saturating $y_{i+1}$, there is no need to continue the operation. Moreover,
since $M$ is a matching, all $x_{i}$ and $y_{i}$ are distinct. Therefore, this
operation will be stopped after finitely many steps. So, when the replacement
is done, the resulting minimum mitigating set is a matching and the claim is
proved.

We next prove that (1) and (3) are equivalent. Let $S\subseteq V(G)$, and set
$H(S)=G[N[S]]$. It is clear that if $G$ has a matching that saturates
$\operatorname{\rm Core}(G)$, then (3) holds. For the converse, set
$n=|V(G)|$. Let $A=G[\operatorname{\rm Core}(G)]$ and $B=G\setminus A$. By
contradiction assume that $G$ has no matching that covers $A$. Therefore, by
Lemma 2.2, there exists $S\subseteq V(G)$ such that

$o_{G[A]}(G\setminus S)\geq|S|+1\,,$

Suppose $C_{1},C_{2},\ldots,C_{|S|+1}\subseteq A$ are some odd components
contained in $A$. Let $C=\bigcup_{i=1}^{|S|+1}C_{i}$. Clearly,
$|V(H(C))|\leq|S|+|V(C)|$. Since $V(C_{i})$ has odd cardinality and consists
of vertices of degree $\Delta$, we have

$\operatorname{{\rm
es}_{\Delta}}\left(H(C_{i})\right)\geq\frac{|V(C_{i})|+1}{2}\,.$

Therefore,

$\operatorname{{\rm
es}_{\Delta}}\left(H(C)\right)\geq\sum_{i=1}^{|S|+1}\frac{|V(C_{i})|+1}{2}\geq\frac{|V(C)|}{2}+\frac{|S|+1}{2}>\frac{|V(C)|+|S|}{2}\geq\frac{|V(H(C))|}{2}\,,$

a contradiction and we are done. ∎

##  3 Graph’s regularization and its applications

In this section we prove that to derive an upper bound of the form
$\operatorname{{\rm es}_{\Delta}}(G)\leq c|V(G)|$ for an arbitrary graph,
where $c$ is a given constant, it suffices to prove the bound for regular
graphs.

For a graph $G$ we construct its regularization $R(G)$ as follows. If $G$ is
regular, then set $R(G)=G$. Assume now that $G$ is not regular and set
$A_{G}=V(G)\setminus\operatorname{\rm Core}(G)$. Then the graph $G^{(1)}$ is
obtained from two disjoint copies of $G$, say $G^{\prime}$ and
$G^{\prime\prime}$, by adding a matching between the corresponding vertices in
$A_{G^{\prime}}$ and $A_{G^{\prime\prime}}$. Note that
$\Delta(G^{(1)})=\Delta(G)$ and $\delta(G^{(1)})=\delta(G)+1$. If $G^{(1)}$ is
not yet regular, we repeat the same construction on $G^{(1)}$ to construct
$G^{(2)}$. Repeating the construction $\Delta(G)-\delta(G)$ times we arrive at
the regularization $R(G)$ of $G$:

$R(G)=G^{(\Delta(G)-\delta(G))}\,,$

which is a $\Delta(G)$-regular graph.

A key property of $R(G)$ is the following.

######  Lemma 3.1.

If $G$ is a graph, then

$\frac{|V(R(G))|}{\operatorname{{\rm
es}_{\Delta}}(R(G))}\leq\frac{|V(G)|}{\operatorname{{\rm es}_{\Delta}}(G)}\,.$

###### Proof.

There is nothing to prove if $G$ is regular, hence assume in the rest that
$\Delta(G)-\delta(G)\geq 1$. We first claim that

$\frac{|V(G^{(1)})|}{\operatorname{{\rm
es}_{\Delta}}(G^{(1)})}\leq\frac{|V(G)|}{\operatorname{{\rm
es}_{\Delta}}(G)}\,.$

Let $M$ be a mitigating set of $G^{(1)}$ and let $G^{\prime}$ and
$G^{\prime\prime}$ be the two copies of $G$ in $G^{(1)}$. As every edge
between $G^{\prime}$ and $G^{\prime\prime}$ connects vertices of not-maximum
degree in $G^{\prime}$ and $G^{\prime\prime}$, the sets $M\cap E(G^{\prime})$
and $M\cap E(G^{\prime\prime})$ are mitigating sets of $G^{\prime}$ and
$G^{\prime\prime}$ respectively. Thus, $\operatorname{{\rm
es}_{\Delta}}(G^{(1)})\geq 2\operatorname{{\rm es}_{\Delta}}(G)$. Since
$|V(G^{(1)})|=2|V(G)|$, the claim is proved. Proceeding by induction we
analogously infer that

$\frac{|V(G^{(i)})|}{\operatorname{{\rm
es}_{\Delta}}(G^{(i)})}\leq\frac{|V(G)|}{\operatorname{{\rm es}_{\Delta}}(G)}$

holds for each $i\in\\{2,\ldots,\Delta(G)-\delta(G)\\}$. Thus the assertion. ∎

The announced reduction to regular graphs now reads as follows.

######  Theorem 3.2.

If there exists a constant $0<c_{\Delta}<1$, such that $\operatorname{{\rm
es}_{\Delta}}(H)\leq c_{\Delta}|V(H)|$ holds for every $\Delta$-regular graph
$H$, then $\operatorname{{\rm es}_{\Delta}}(G)\leq c_{\Delta}|V(G)|$ holds for
every graph $G$ with $\Delta(G)=\Delta$.

###### Proof.

Let $G$ be an arbitrary graph with $\Delta(G)=\Delta$. As there is nothing to
prove if $G$ is regular, assume this is not the case. Then by Lemma 3.1 and
the theorem’s assumption we get

$\displaystyle\operatorname{{\rm es}_{\Delta}}(G)$
$\displaystyle\leq\operatorname{{\rm
es}_{\Delta}}(R(G))\frac{|V(G)|}{|V(R(G))|}\leq
c_{\Delta}|V(R(G))|\frac{|V(G)|}{|V(R(G))|}=c_{\Delta}|V(G)|$

and we are done. ∎

Another applications of Lemma 3.1 is the following bound on the $\Delta$-edge
stability number of a graph in terms of its odd girth.

######  Theorem 3.3.

If $G$ be a graph of order $n$ and ${\rm og}(G)=2k+1$, $k\geq 1$, then
$\operatorname{{\rm es}_{\Delta}}(G)\leq\frac{k+1}{2k+1}n$.

###### Proof.

We claim that ${\rm og}(G^{(i)})\geq 2k+1$ holds for each
$i\in[\Delta-\delta]$. Consider first $G^{(1)}$ and let $W_{1}$ be an
arbitrary odd closed walk in it. Assume that $W_{1}$ passes through
$G^{\prime}$ as well as through $G^{\prime\prime}$. Let
$e=u^{\prime}u^{\prime\prime}$ and $f=v^{\prime}v^{\prime\prime}$ be two edges
of $W_{1}$ between $G^{\prime}$ and $G^{\prime\prime}$ (where
$u^{\prime},v^{\prime}\in V(G^{\prime})$ and
$u^{\prime\prime},v^{\prime\prime}\in V(G^{\prime\prime})$) occurring
consecutively on $W_{1}$. Let
$W^{\prime\prime}_{u^{\prime\prime}v^{\prime\prime}}$ be the
$u^{\prime\prime},v^{\prime\prime}$-subwalk of $W_{1}$. Then
$W^{\prime\prime}_{u^{\prime\prime}v^{\prime\prime}}$ is contained in
$G^{\prime\prime}$. Now replace the
$u^{\prime}-u^{\prime\prime}-W^{\prime\prime}_{u^{\prime\prime}v^{\prime\prime}}-v^{\prime\prime}-v^{\prime}$
subwalk of $W_{1}$ by the walk
$u^{\prime}-W^{\prime}_{u^{\prime}v^{\prime}}-v^{\prime}$, where
$W^{\prime}_{u^{\prime}v^{\prime}}$ is the isomorphic copy of
$W^{\prime\prime}_{u^{\prime\prime}v^{\prime\prime}}$ in $G^{\prime}$.
Repeating this process if necessary, we arrive at a closed walk of $G^{(1)}$
which lies completely in $G^{\prime}$ and is shorter (or of equal length if
$W_{1}$ already lies completely in $G^{\prime}$) than $W_{1}$. As $G^{\prime}$
is isomorphic to $G$, this proved the claim for $G^{(1)}$. The argument for
$G^{(i)}$, $i\in\\{2,\ldots,\Delta-\delta\\}$ is then analogous.

$R(G)$ is a regular graph, and it was proved by Hajnal [9] and Tutte [18] (see
also [12]) that such a graph has a $\\{1,2\\}$-factor $F$. Clearly for any
component $C$ of $F$, one can remove $\lceil{\frac{|V(C)|}{2}}\rceil$ edges of
$C$ which saturate $V(C)$. Since
$\lceil{\frac{|V(C)|}{2}}\rceil\leq\frac{k+1}{2k+1}|V(C)|$, we obtain

$\operatorname{{\rm es}_{\Delta}}(R(G))\leq\frac{k+1}{2k+1}|V(R(G))|\,.$

By Lemma 3.1 we then get

$\displaystyle\operatorname{{\rm es}_{\Delta}}(G)$
$\displaystyle\leq\operatorname{{\rm
es}_{\Delta}}(R(G))\frac{|V(G)|}{|V(R(G))|}\leq\frac{k+1}{2k+1}|V(R(G))|\frac{|V(G)|}{|V(R(G))|}=\frac{k+1}{2k+1}|V(G)|$

and we are done. ∎

##  4 The regular case

In view of Theorem 3.2, in this section we take a closer look to regular
graphs. For this sake we first recall the following fundamental result due to
Henning and Yeo.

######  Theorem 4.1 (Henning and Yeo, [10]).

Let $G$ be a connected, $k$-regular graph of order $n$. If $k\geq 2$ is even,
then

$\alpha^{\prime}(G)\geq\min\left\\{\frac{(k^{2}+4)n}{2(k^{2}+k+2)},\frac{n-1}{2}\right\\}\,,$

and if $k\geq 3$ is odd, then

$\alpha^{\prime}(G)\geq\frac{(k^{3}-k^{2}-2)n-2k+2}{2(k^{3}-3k)}\,.$

Moreover, both bounds are tight.

From Theorem 4.1 we can deduce the following consequence.

######  Corollary 4.2.

Let $G$ be a connected, $k$-regular graph of order $n$. If $k\geq 2$ is even,
then

$\operatorname{{\rm
es}_{\Delta}}(G)\leq\max\left\\{\left(1-\frac{k^{2}+4}{2(k^{2}+k+2)}\right)n,\frac{n+1}{2}\right\\}\,,$

and if $k\geq 3$ is odd, then

$\operatorname{{\rm
es}_{\Delta}}(G)\leq\frac{(k^{3}+k^{2}-6k+2)n+2k-2}{2(k^{3}-3k)}\,.$

Moreover, both bounds are tight.

###### Proof.

By Theorem 1.1 and the assumption that $G$ is regular, we have
$\operatorname{{\rm es}_{\Delta}}(G)=n-\alpha^{\prime}(G)$. Therefore, if $k$
is even, then using Theorem 4.1 we can estimate as follows:

$\displaystyle\operatorname{{\rm es}_{\Delta}}(G)$ $\displaystyle\leq
n-\min\left\\{\frac{(k^{2}+4)n}{2(k^{2}+k+2)},\frac{n-1}{2}\right\\}$
$\displaystyle=\max\left\\{n-\frac{(k^{2}+4)n}{2(k^{2}+k+2)},n-\frac{n-1}{2}\right\\}$
$\displaystyle=\max\left\\{\left(1-\frac{k^{2}+4}{2(k^{2}+k+2)}\right)n,\frac{n+1}{2}\right\\}\,.$

The estimate for odd $k$ is derived analogously.

The tightness follows by the tightness of the estimates from Theorem 4.1. ∎

As discussed in [10], the bound $(n-1)/2$ from Theorem 4.1 is only necessary
to cover some cases when $n$ is very small or $k=2$. In particular, it is not
needed for $k\geq 4$, cf. [10, Corollary 1]. Therefore, we can also state the
following the following easier-to-read corollary for all “non-trivial” even
$k$.

######  Corollary 4.3.

If $G$ is a connected graph of order $n$ with maximum degree $k$, where $k\geq
4$ is even, then

$\operatorname{{\rm
es}_{\Delta}}(G)\leq\left(1-\frac{k^{2}+4}{2(k^{2}+k+2)}\right)n\,.$

If $k=4$, then the bound of Corollary 4.3 reads as $\operatorname{{\rm
es}_{\Delta}}(G)\leq\frac{6}{11}n$. We next construct $2$-connected,
$4$-regular graphs for which the equality holds in this bound. Let
$H_{i}=K_{5}\setminus e$, $i\in[2k]$, and let $G_{k}$ be the graph of order
$n=11k$ as shown in Fig. 1.

$\dotsc$$H_{1}$$H_{2}$$H_{4}$$H_{3}$$H_{5}$$H_{6}$$H_{2k-1}$$H_{2k}$$v_{1}$$v_{2}$$v_{k}$$e$
Figure 1: The graph $G_{k}$

We claim that $\alpha^{\prime}(G)=5k$ and $\operatorname{{\rm
es}_{\Delta}}(G)=6k$. Since $\alpha^{\prime}(K_{5}\setminus e)=2$, and every
matching of $G$ has at most one edge incident with $v_{j}$, $j\in[k]$, we
infer that $\alpha^{\prime}(G)\leq 2(2k)+k=5k$. Note that a $2$-matching of
each $H_{i}$ together with the bold edges from Fig. 1 represent a maximum
matching of size $5k$ in $G$. So, $\alpha^{\prime}(G)=5k$. Since $G$ is
4-regular, by Theorem 1.1, $\operatorname{{\rm es}_{\Delta}}(G)=6k$ and hence
the conclusion is reached after a direct computation.

From the second estimate of Corollary 4.2, we can deduce also the following
consequence.

######  Corollary 4.4.

For each $\epsilon>0$ and sufficiently large $n$, for every graph $G$ of order
$n$ with odd maximum degree $k$, we have

$\operatorname{{\rm
es}_{\Delta}}(G)\leq\left(\frac{k^{3}+k^{2}-6k+2}{2(k^{3}-3k)}+\epsilon\right)n.$

We know the following function is monotone

$f(k)=\frac{k^{3}+k^{2}-6k+2}{2(k^{3}-3k)}\,.$

Moreover,

$\lim_{k\rightarrow\infty}f(k)=\frac{1}{2}\,,$

By Corollary 4.3 for $k>2$ even, we have

$\operatorname{{\rm es}_{\Delta}}(G)\leq\frac{n+1}{2}.$

Combining Corollaries 4.3 and 4.4 with the above discussion, and having
Theorem 3.2 in mind, we get the following result by setting $k=3$.

######  Corollary 4.5.

For each $\epsilon>0$ and sufficiently large $n$, for every connected graph
$G$ of order $n$, we have

$\operatorname{{\rm es}_{\Delta}}(G)\leq\left(\frac{5}{9}+\epsilon\right)n.$

##  5 Graphs with the $\Delta$-edge stability number at most half the order

In this section we are interested in families of graphs for which the
$\Delta$-edge stability number is bounded from the above by one half of the
order. First, as a consequence of Theorem 2.1(ii), this holds true for
bipartite graphs.

######  Corollary 5.1.

If $G$ is a bipartite graph of order $n$, then $\operatorname{{\rm
es}_{\Delta}}(G)\leq n/2$.

Our next goal is to show that this bound also holds for each graph $G$ whose
$G[\operatorname{\rm Core}(G)]$ is Class 1. To this end, let us first prove
the following.

######  Theorem 5.2.

Let $G$ be a graph with maximum degree $\Delta$. If $G[\operatorname{\rm
Core}(G)]$ has a proper $\Delta$ edge-coloring, then $G$ has a matching that
saturates $\operatorname{\rm Core}(G)$.

###### Proof.

Let $n=|V(G)|$. Let $A=G[\operatorname{\rm Core}(G)]$ and $B=G\setminus V(A)$.
Suppose that $G$ has no matching that saturates $A$. By Lemma 2.2, there
exists $S\subseteq V(G)$ such that

$o_{G[A]}(G\setminus S)\geq|S|+1$

Now, we claim that if $C\subseteq A$ is an odd component of $G\setminus S$,
then

$e_{G}(C,S)\geq\Delta.$ (2)

Consider a proper $\Delta$-edge coloring of $A$ and extend it to a coloring of
$G\setminus E(B)$ such that for every $u\in A$, all edges adjacent to $u$ have
$\Delta$ distinct colors.

If there are at most $\Delta-1$ edges with one endpoint in $V(C)$ and another
in $S$, then there exists a color $t$ which has not appeared on these edges.
Since every vertex in $C$ has degree $\Delta$, the color $t$ appears at each
vertex of $C$. Therefore, the edges with color $t$ in $C$ form a perfect
matching in $C$, a contradiction, and the claim is proved.

By the claim, we have

$e_{G}(A\setminus S,S)\geq\left(|S|+1\right)\Delta.$

Now, by the Pigeonhole Principle, there exists $u\in S$ such that

$e_{G}(A,\left\\{u\right\\})\geq\Delta+1$

which is a contradiction. ∎

A matching that saturates every vertex of $\operatorname{\rm Core}(G)$ is
clearly a mitigating set, hence from Theorem 5.2 we immediately get:

######  Corollary 5.3.

If $G$ is a graph of order $n$ such that $G[\operatorname{\rm Core}(G)]$ is
Class 1, then $\operatorname{{\rm es}_{\Delta}}(G)\leq\frac{n}{2}$. In
particular, if $G$ is Class 1 graph, then $\operatorname{{\rm
es}_{\Delta}}(G)\leq\frac{n}{2}$.

In our final result, we prove that also in graphs with large maximum degree
the $\Delta$-edge stability number is bounded from the above by one-half of
the order. To prove the result we state the following lemma for which we
recall that a graph is factor critical if every vertex deleted subgraph has a
perfect matching.

######  Lemma 5.4.

If $G$ does not have a perfect matching and $S\subseteq V(G)$ is the biggest
set such that

$o(G\setminus S)>|S|,$ (3)

then each component of $G\backslash S$ is factor critical.

###### Proof.

Suppose that $C$ is a component of $G\setminus S$ of even order and $v\in C$.
Note that, $C\setminus\\{v\\}$ has at least one odd component. Therefore,
$S\cup\\{v\\}$ satisfies (3), a contradiction. So, $G\setminus S$ has no even
component. Suppose $C$ is an odd component of $G\setminus S$ which is not
factor critical. Thus if we remove $v\in C$ from $C$, the remaining vertices
do not have a perfect matching. Hence, there is $S^{\prime}\subseteq
C\setminus\\{v\\}$ such that $o\left(G[C\setminus\\{v\\}]\setminus
S^{\prime}\right)>|S^{\prime}|+1$. Thus, $S\cup S^{\prime}\cup\\{v\\}$
satisfies (3), a contradiction. ∎

Our final result now reads as follows.

######  Theorem 5.5.

Let $G$ be a connected graph of order $n$ with maximum degree $\Delta$. If
$\Delta\geq\frac{n-2}{3}$, then $es_{\Delta}(G)\leq\lceil\frac{n}{2}\rceil$.

###### Proof.

Let $A=V(Core(G))$ and $B=V(G)\backslash A$. If there exists a matching in $G$
which saturates $A$, then we get the result. Now, assume $G$ does not contain
such matchings. So, by Lemma 2.2, there exists $S\subseteq V(G)$ such that
$o_{G[A]}(G\setminus S)\geq|S|+1$. Thus, there exist at least $|S|+1$ odd
components in $G\setminus S$ that are contained in $A$. We name them as
$C_{1},C_{2},\ldots,C_{|S|+1}$.

We claim that if $C$ is a component in $G\backslash S$ whose vertices are
contained in $A$ and $e\left(V(C),S\right)<\Delta$, then the order of $C$ is
at least $\Delta+1$, moreover, there exists $v\in V(C)$ such that
$N[v]\subseteq V(C)$. First, suppose that $C$ is of order at least $\Delta$.
If every vertex of $C$ has a neighbor in $S$, then it is clear that
$e(V(C),S)\geq\Delta$, a contradiction. So, there exists a vertex $v\in C$
such that $N[v]\subseteq V(C)$. Thus, $|V(C)|\geq\Delta+1$, as desired. If
$|V(C)|<\Delta$, since every vertex of $C$ have degree $\Delta$, so for every
$u\in V(C)$ we have $e(\\{u\\},S)\geq\Delta-|V(C)|+1$. Hence
$e(V(C),S)\geq|V(C)|(\Delta-|V(C)|+1)\geq\Delta$, contradiction. So the claim
is proved.

Note that if $e(V(C),S)\geq\Delta$ for every
$C\in\\{C_{1},\ldots,C_{|S|+1}\\}$, then $e(\cup V(C_{i}),S)\geq\Delta(|S|+1)$
and by the pigeonhole principal, there exists $w\in S$ such that
$d(w)\geq\Delta+1$, a contradiction.

Now, since $\Delta\geq\frac{n-2}{3}$, if $C$ is a component of $G\backslash S$
and $e(V(C),S)<\Delta$, then by the claim we have $|V(C)|\geq\frac{n+1}{3}$.
Hence, we have at most two $C_{i}$ with this property that
$e(V(C_{i}),S)<\Delta$, say $C_{1}$ and $C_{2}$. Let
$L=\bigcup_{i=1}^{|S|+1}V(C_{i})$ and consider two cases.

Case 1. $|V(C_{1})|>\Delta$ and for every $i>1$, $|V(C_{i})|\leq\Delta$.
So, by the claim, $e(L\setminus V(C_{1}),S)\geq\Delta|S|$. On the other hand
since for every $s\in S$, $d(s)\leq\Delta$, we have $e(L\setminus
V(C_{1}),S)\leq\Delta|S|$. Hence, $e(L\setminus V(C_{1}),S)=\Delta|S|$ and it
means that all neighbors of each vertex of $S$ is in
$V(C_{2}),\ldots,V(C_{|S|+1})$. So, $C_{1}$ is a component of $G$ which
contradicts the connectivity of $G$.

Case 2. $|V(C_{1})|>\Delta$, $|V(C_{2})|>\Delta$, and for every $i>2$,
$|V(C_{i})|\leq\Delta$.
Since, $|V(C_{1})|\geq\frac{n+1}{3}$ and $|V(C_{2})|\geq\frac{n+1}{3}$, so
$|V(G)\setminus\left(V(C_{1})\cup V(C_{2})\right)|<\frac{n-1}{3}$. If there
exists a vertex $u\in V(G)\setminus\left(V(C_{1})\cup V(C_{2})\right)$ of
degree $\Delta$, since $N[u]\subseteq V(G)\setminus\left(V(C_{1})\cup
V(C_{2})\right)$ and $|N[u]|>\frac{n}{3}$, we get a contradiction. So,
$L\setminus\left(V(C_{1})\cup V(C_{2})\right)=\varnothing$ and thus, $|S|=1$.

Note that if we choose the set $S$ with the maximum size, by Lemma 5.4 all
components of $G\backslash S$ that are in $A$ and have odd orders are factor
critical. Let $S=\\{s\\}$. We choose two arbitrary edges $su$ and $sv$ such
that $u\in V(C_{1})$ and $v\in V(C_{2})$. As $C_{1}$ and $C_{2}$ are factor
critical, there exist matchings $M$ and $N$ that saturate vertices of
$C_{1}\backslash\\{u\\}$ and $C_{2}\backslash\\{v\\}$, respectively. Since all
vertices of degree $\Delta$ are in $L\cup S$, it is clear that $M\cup
N\cup\\{su,sv\\}$ is a mitigating set for $G$. Note that
$|M|+|N|+|\\{su,sv\\}|=\frac{|L|+2}{2}\leq\frac{n+1}{2}$, thus
$\operatorname{{\rm es}_{\Delta}}(G)\leq\frac{n+1}{2}$ and we are done. ∎

######  Remark 5.6.

To see that the bound $\Delta\geq\frac{n-2}{3}$ of Theorem 5.5 cannot be
lowered in general, consider the following example. For each odd $t\geq 7$,
let $G_{t}$ be the graph constructed as follows. Take three disjoint copies of
$K_{t}$, remove one edge from each of them, add a vertex $u$, and join $u$ to
the endpoints of the deleted edges, see Fig. 2.

$e$$K_{t}$$e$$K_{t}$$e$$K_{t}$$u$ Figure 2: The graph $G_{t}$

In $G_{t}$ we need at least $\frac{t+1}{2}$ edges to saturate the vertices of
each $K_{t}$. Hence, $\operatorname{{\rm
es}_{\Delta}}(G)\geq\frac{3(t+1)}{2}$. Setting $n=|V(G_{t})|$, we have
$n=3t+1$. As $t\geq 7$ we have $\Delta(G_{t})=\frac{n-4}{3}$. In summary,

$\Delta(G_{t})=\frac{n-4}{3}<\frac{n-2}{3}\quad{\rm
and}\quad\operatorname{{\rm es}_{\Delta}}(G_{t})\geq\frac{n}{2}+1\,,$

hence the assumption on the maximum degree in Theorem 5.5 is tight.

As in a graph $G$ we have $\Delta(G)\geq\frac{2|E(G)|}{|V(G)|}$, Theorem 5.5
yields:

######  Corollary 5.7.

If $G$ is a graph of order $n$ and size at least $\frac{n(n-2)}{6}$, then
$es_{\Delta}(G)\leq\lceil\frac{n}{2}\rceil$.

## Acknowledgements

This research was in part supported by a grant from IPM (No. 1402050012).
Sandi Klavžar was supported by the Slovenian Research Agency ARIS (research
core funding P1-0297 and projects J1-2452, N1-0285).

## References

  * [1] S. Akbari, A. Beikmohammadi, S. Klavžar, N. Movarraei, On the chromatic vertex stability number of graphs, European J. Combin. 102 (2022) Paper 103504.
  * [2] S. Akbari, A. Beikmohammadi, B. Brešar, T. Dravec, M.M. Habibollahi, N. Movarraei, On the chromatic edge stability index of graphs, European J. Combin. 111 (2023) Paper 103690.
  * [3] S. Akbari, S. Klavžar, N. Movarraei, M. Nahvi, Nordhaus-Gaddum and other bounds for the chromatic edge-stability number, European J. Combin. 84 (2020) Paper 103042.
  * [4] S. Alikhani, M.R. Piri, On the edge chromatic vertex stability number of graphs, AKCE Int. J. Graphs Comb. 20 (2023) 29–34.
  * [5] P. Borg, Decreasing the maximum degree of a graph, Discrete Math. 345 (2022) Paper 112994.
  * [6] P. Borg, K. Fenech, Reducing the maximum degree of a graph by deleting vertices, Australas. J. Combin. 69 (2017) 29–40.
  * [7] P. Borg, K. Fenech, Reducing the maximum degree of a graph by deleting edges, Australas. J. Combin. 73 (2019) 247–260.
  * [8] B. Brešar, S. Klavžar, N. Movarraei, Critical graphs for the chromatic edge-stability number, Discrete Math. 343 (2020) Paper 111845.
  * [9] A. Hajnal, A theorem on $k$-saturated graphs, Canadian J. Math. 17 (1965) 720–724.
  * [10] M.A. Henning, A. Yeo, Tight lower bounds on the size of a maximum matching in a regular graph, Graphs Combin. 23 (2007) 647–657.
  * [11] B. Jackson, Cycles through vertices of large maximum degree, J. Graph Theory 19 (1995) 157–168.
  * [12] M. Kano, Factors of regular graphs, J. Combin. Theory Ser. B 41 (1986) 27–36.
  * [13] A. Kemnitz, M. Marangio, On the $\rho$-edge stability number of graphs, Discuss. Math. Graph Theory 42 (2022) 249–262.
  * [14] A. Kemnitz, M. Marangio, On the vertex stability numbers of graphs, Discrete Appl. Math. 344 (2024) 1–9.
  * [15] A. Kemnitz, M. Marangio, N. Movarraei, On the chromatic edge stability number of graphs, Graphs Combin. 34 (2018) 1539–1551.
  * [16] M. Knor, M. Petruševski, R. Škrekovski, On chromatic vertex stability of $3$-chromatic graphs with maximum degree $4$, Discrete Math. Lett. 10 (2022) 75–80.
  * [17] H. Lei, X. Lian, X. Meng, Y. Shi, Y. Wang, On critical graphs for the chromatic edge-stability number, Discrete Math. 346 (2023) Paper 113307.
  * [18] W.T. Tutte, The factors of graphs, Canad. J. Math. 4 (1952) 314–328.
  * [19] V.G. Vizing, On an estimate of the chromatic class of a $p$-graph, Diskret. Analiz 3 (1964) 25–30.