G-S

    Gauss-Seidel
JF-INK-GMRES

    Jacobian-free Inexact-Newton-Krylov GMRES
JF-INK-Arnoldi

    Jacobian-free Inexact-Newton-Krylov Arnoldi
QIN

    Quasi-Inverse-Newton
AFI

    Abstract Functional Interface
SV

    State Variable
_NARep_

    _Non/̄Anonymous Rep_
_SS_

    _State/̄Sharing_
_CS_

    _Channel/̄Sharing_
_DARep_

    _Dependency/̄Aware Replication_
WAN

    Wide Area Network
INTERNET

    Internet network
SIFS

    Short Inter-Frame Space
STA

    Station in Wi-Fi network
SW

    Switch
TOS

    Type of Service
TSO

    Transmission System Operator
UDP

    User Datagram Protocol
$MF$

    malicious failure state
$MFF$

    malicious failure free state
$T\\_MF$

    permanence time in the state $MF$
$T\\_MFF$

    permanence time in the state $MFF$
$P\\_CMF$

    probability of choosing content malicious failure in the state $MFF$
$P\\_TMF$

    probability of choosing timing malicious failure in the state $MFF$
$MFSi$

    state representing the $i$-th severity level of the malicious failure in the state $MFF$
$MFSn$

    state representing the $n$-th worst severity level of the malicious failure in the state $MFF$
$T\\_D$

    time to execute the task when a component is in the state $MFF$
$T\\_L$

    threshold for the time to execute a task when a component is in the state $MFF$, used to specify when the result of the task has to be considered lost
$P\\_MFSi$

    probability of reaching the $i$-th severity level from the state $MFF$
PSO

    particle swarm optimization
$TNMFS$

    time to move to the next severity level
$TPMFS$

    time to move to the previous severity level
$V$

    voltage
$V_{\\_}i(t)$

    voltage on bus $i$ at time $t$
VR

    Voltage Regulator
PFP

    Power Flow Problem
PFE

    Power Flow Equation
SG

    Smart Grid
$\delta$

    voltage phase angle
$\delta_{\\_}h$

    voltage phase angle of the node $h$
$P_{\\_}h$

    active power of the node $h$
$Q_{\\_}h$

    reactive power of the node $h$
$V_{\\_}h$

    voltage magnitude of the node $h$
CSYS

    Central System
CMCS

    Central Management and Control System
BUS

    Bus-Bar
$\mathcal{BUS}$

    Bus-Bar
BG

    Bulk Generator
DG

    Distributed Generator
DER

    Distributed Energy Resource
PVP

    Photovoltaic Plant
WP

    Wind Power Plant
DS

    Distributed Storage unit
CB

    Capacitor Bank
$\mathcal{CB}$

    Capacitor Bank
$DS^{auto}_{\\_}i$

    the autonomy of the storage unit on the node $i$
$DS^{c}_{\\_}i(t)$

    The current amount of electric charge stored at time $t$ on the strorage unit on the node $i$
$DS^{cmax}_{\\_}i$

    maximum capacity of the storage unit on the node $i$
$DS_{\\_}i$

    Distributed Storage unit (battery) on the bus $i$
DSO

    Distribution System Operator
$DS^{size}_{\\_}i$

    the size of the strorage unit on the node $i$
$V$

    voltage
ECS

    Electrical Charging Station
CS

    Charging Spot
EDCA

    Enhanced Distributed Channel Access
EI

    Electrical Infrastructure
EO

    Evolving Objects
EPS

    Electrical Power System
ERP

    Extended Rate PHYs
EV

    Electrical Vehicle
F

    frequency
FG

    Flexible Generator
$FG_{\\_}i$

    Flexible Generator on the bus $i$
FL

    Flexible Load
L

    Load
$\mathcal{FL}$

    Flexible Load
$FL_{\\_}i$

    Flexible Load on the bus $i$
$FP^{D}_{\\_}i(\cdots)$

    Flexibility Pattern for power demand
$G^{F}_{\\_}i(t)$

    generation forecast at time $t$ for generator on bus $i$
HES

    Head-end System
HV

    High Voltage
HV-EI

    High Voltage Electrical Infrastructure
HVG

    Power source corresponding to the high-voltage transmission lines feeding a primary substation
I

    Current Flow
ICT

    Information and Communications Technologies
$I_{\\_}l^{max}$

    maximum current flow that a power line $l$ can carry at time $t$ whitout being overloaded
$I_{\\_}l$

    current flow associated to line $l$
$I_{\\_}l(t)$

    current flow associated to line $l$ at time $t$
IP

    Internet Protocol
IFL

    Inflexible Load
AN

    Access Network
LC

    Logical Controller
$L_{\\_}i$

    Non-Flexible Load on bus $i$
LLC

    Logical Link Control
LV

    Low Voltage
LV-EI

    Low Voltage Electric Infrastructure
LV-MCS

    Low Voltage Monitoring and Control System
LVGC

    Low Voltage Grid Control
LVL

    Load corresponding to a secondary substation fed by the medium-voltge grid
MAC

    Medium Access Control
MCS

    Monitoring and Control System
MG

    Micro-Mini Generator
MTU

    Maximum Transmission Unit
MV

    Medium Voltage
MV-EI

    Medium Voltage Electric Infrastructure
MV-MCS

    Medium Voltage Monitoring and Control System
MVG

    Power source corresponding to a medium-voltage distribution line feeding a secondary substation
MVGC

    Medium Voltage Grid Control
OLTC

    On Load Tap Changer
$\mathcal{OLTC}$

    On Load Tap Changer
OPF

    Optimal Power Flow
$P$

    active power
$P^{D}_{\\_}i(t)$

    actual power demand (active power) that is met at time $t$ for load on node $i$
$P^{G}_{\\_}i(t)$

    actual active power generated on node $i$ at time $t$
$P_{\\_}h(t)$

    active power on bus $h$ at time $t$
PHY

    physical (layer)
PL

    Power Line
PLCP

    Physical Layer Convergence Protocol
$PL_{\\_}l$

    power line $l$
$P^{max}_{\\_}i$

    maximum active power that a generator can supply on bus $i$
Q

    reactive power
$Q^{D}_{\\_}i(t)$

    actual reactive power demand at time $t$ for load on node $i$
$Q^{G}_{\\_}i(t)$

    actualreactive power generated on node $i$ at time $t$
$Q_{\\_}h(t)$

    reactive power on bus $h$ at time $t$
$Q^{max}_{\\_}i$

    maximum reactive power that a generator can supply on bus $i$
QoS

    Quality of Service
RES

    Renewable Energy System
$\mathcal{RES}$

    Renewable Energy System
T

    Transformer
$T_{\\_}G$

    oriented graph representing the topology of EI
$\theta_{\\_}V$

    phase angle of voltage V
LV_LC_ATTACK_SAN

    Template SAN model representing the malicious failures of generic logical controller LC at low voltage level caused by an attack to the LC
AN_SAN

    Template SAN model representing a generic Access Network AN
LVGC_ATTACK_SAN

    Template SAN model representing the malicious failures of a generic LVGC caused by an attack to the LVGC
AN_ATTACK_SAN

    Template representing the malicious failures of a generic Access Network AN caused by an attack to the AN
LV_ESTATE_SAN

    Atomic SAN model representing the update of the state of Low Voltage Electric Infrastructure (LV-EI) directly triggered by failures (outages) in LV-EI
LV_EI_INIT_SAN

    Atomic SAN model representing the initialization of the SAN models defined in LV_EI_M
LV_MCS_INIT_SAN

    Atomic SAN model representing the initialization of the models defined in LV_MCS_M
LV_SP_SAN

    Template SAN model representing the actuation of the new set points triggered by LVGC
LV_NCC_SAN

    Template SAN model representing the non coordinated control actions for an area under the control of LVGC
LV_NODE1_M

    Template model representing the generic node starting from a line at low voltage level
LV_NODE2_M

    Template model representing the generic node ending to a line at low voltage level
LVGC_SAN

    Template SAN model representing a generic LVGC
LV_ARC_M

    Template model representing a generic arc at low voltage level
LV_PL_SAN

    Template SAN model representing a generic power line PL at low voltage level
ARC

    Generic arc component
NODE

    Generic node component
MV_ESTATE_SAN

    Atomic SAN model representing the update of the state of Medium Voltage Electric Infrastructure (MV-EI) directly triggered by failures (outages) in MV-EI
MV_PL_SAN

    Template SAN model representing a generic power line PL at medium voltage level
MV_SW_SAN

    Template SAN model representing a generic Switch at medium voltage level
MV_VR_SAN

    Template SAN model representing a generic Voltage Regulator at medium voltage level
MV_BUS1_SAN

    Template SAN model representing a generic Bus-Bar at medium voltage level
MV_BUS2_SAN

    Template SAN model representing a generic Bus-Bar at medium voltage level
MV_BG_SAN

    Template SAN model representing a generic Bulk Generator at medium voltage level
MV_DS_SAN

    Template SAN model representing a generic Distributed Generator at medium voltage level
MV_FG_SAN

    Template SAN model representing a generic Flexible Generator at medium voltage level
MV_DS_SAN

    Template SAN model representing a generic DS at medium voltage level
MV_L_SAN

    Template SAN model representing a generic flexible or inflexible load at medium voltage level
MV_FL_SAN

    Template SAN model representing a generic Flexible Load at medium voltage level
MV_OLTC_SAN

    Template SAN model representing a generic OLTC at medium voltage level
MV_CB_SAN

    Template SAN model representing a generic Capacitor Bank at medium voltage level
CSYS_SAN

    Atomic SAN model representing the central system
WAN_SAN

     SAN model representing the WAN associated to CMCS
INTERNET

     SAN model representing the INTERNET
CSYS_ATTACK_SAN

     SAN model representing the malicious failures of CSYS caused by an attack
CMCS_WAN_ATTACK_SAN

     SAN model representing the malicious failures of CMCSWAN caused by an attack
INTERNET_ATTACK_SAN

     SAN model representing the malicious failures of INTERNET caused by an attack
MV_MCS_INIT_SAN

    Atomic SAN model representing the initialization of the models defined in MV_MCS_M
MV_EI_INIT_SAN

    Atomic SAN model representing the initialization of the SAN models defined in MV_EI_M
MV_SP_SAN

    Template SAN model representing the actuation of the new set points triggered by MVGC
MVGC_SAN

    Template SAN model representing a generic MVGC
WAN_ATTACK_SAN

    Template representing the malicious failures of a generic Wide Area Network WAN caused by an attack to the WAN
MVGC_ATTACK_SAN

    Template SAN model representing the malicious failures of a generic MVGC caused by an attack to the MVGC
WAN_SAN

    Template SAN model representing a generic Wide Area Network WAN
MV_LC_ATTACK_SAN

    Template SAN model representing the malicious failures of generic logical controller LC at medium voltage level caused by an attack to the LC
MV_LC_SAN

    Template SAN model representing a generic logical controller LC
MV_NCC_Ms

    Composed model representing the non coordinated control actions
MV_NCC_SAN

    Template SAN model representing the non coordinated control actions for an area under the control of MVGC
MVGC_M

    Composed model representing a generic MVGC and the malicious failures of MVGC caused by an attack to MVGC
MV_LC_M

    Template model representing a generic logical controller LC at medium voltage level
MV_N1AN2_Ms

    Composed model representing all the arcs of MV-EI with the associated starting and ending nodes
MV_N1AN2_M

    Template model representing a generic arc of MV-EI with the associated starting and ending nodes
MV_NODE1_M

    Template model representing the generic node starting from a line at medium voltage level
MV_NODE2_M

    Template model representing the generic node ending to a line at medium voltage level
MV_ARC_M

    Template model representing a generic arc at medium voltage level
MVGCMs

    Composed model representing all the MVGC at medium voltage level
MV_LC_Ms

    Template model representing all the logical controllers LC at medium voltage level
MV_MCS_M

    Composed model representing MV-MCS
LV_MCS_M

    Composed model representing LV-MCS
MV_EI_M

    Composed model representing MV-EI
LV_EI_M

    Composed model representing LV-EI
CMCS_M

    Composed model representing the Smart Grid at the level of CMCS
MV_M

    Composed model representing the Smart Grid at the medium voltage level
LV_M

    Composed model representing the Smart Grid at the low voltage level
SM

    Smart Meter
CEMS

    Customer Energy Management System
CMCSWAN

    Wide Area Network associated to CMCS

# Enhanced power grid evaluation through
efficient stochastic model/̄based analysis

Giulio Masetti  University of Pisa and ISTI-CNR, Pisa, Italy
<EMAIL_ADDRESS>
###### Abstract

Electrical infrastructures provide services at the basis of a number of
application sectors, several of which are critical from the perspective of
human life, environment or financials. Following the increasing trend in
electricity generation from renewable sources, pushed by the need to meet
sustainable energy goals in many countries, more sophisticated control
strategies are being adopted to regulate the operation of the electric power
system, driving electrical infrastructures towards the so called Smart Grid
scenario. It is therefore paramount to be assisted by technologies able to
analyze the Smart Grid behavior in critical scenarios, e.g. where cyber
malfunctions or grid disruptions occur. In this context, stochastic
model/̄based analysis are well suited to assess dependability and quality of
service related indicators, and continuous improvements in modeling strategies
and system models design are required. Thus, my PhD work addresses this topic
by contributing to study new Smart Grid scenarios, concerning the advanced
interplay between ICT and electrical infrastructures in presence of cyber
faults/attacks, define a new modeling approach, based on modularity and
composition, and start to study how to improve the electrical grid dynamics
representation. In this article these studies are briefly presented and
discussed.

##  I Introduction and research lines description

The complex, digital world around us requires electric power for fundamental
aspects of societal needs, business and consumer activities. It is therefore
widely recognized that electric power systems are among the most critical
infrastructures, whose protection is more and more a priority for many
countries. The increasing trend in electricity generation from renewable
sources, pushed by the need to meet sustainable energy goals in many
countries, poses additional challenges with the need to adopt more
sophisticated control strategies to regulate the operation of the three/̄level
electric power system: transmition, characterized by High Voltage (HV),
distribution, characterized by Medium Voltage (MV), and consumer, typically
characterized by Low Voltage (LV). In this panorama, studies devoted to
analyze the effectiveness of control operations and their ability to face
critical scenarios, such as in presence of failures, are certainly well
motivated.

Model-based analysis is a suitable approach to perform quantitative
estimations of a system since early stages, that is since the design phase.
Therefore, it shows as a powerful means to support design decision, either
allowing to make the most appropriate choice among several available
alternative solutions and to facilitate tuning of parameters when parametric
solutions are employed. Analyses devoted to assess dependability-related
indicators have already appeared in the literature. However, the emphasis has
been mainly given to reliability and availability [1] of Information and
Communications Technologies (ICT) infrastructure employed to guarantee power
supply, without considering explicitly the dynamics of the underlying
Electrical Infrastructure (EI), as for example in [2], or lightly introducing
it. Other studies, instead, focused mainly on the grid infrastructure,
assessing, for instance, survivability [3] or reliability as defined in the
electric sector, i.e., the ability of the power system to deliver electricity
in the quantity and with the quality demanded by users, as in [4], neglecting
the cyber control system and communications.

A more comprehensive viewpoint, targeting the interplay between the cyber
control system with the underlying controlled grid, is needed, especially when
failures occur and propagate their effects from one level to the other. As
contribution in this direction, the SEDC research group at ISTI/̄CNR has been
working in the last years on a stochastic modeling framework to perform
quantitative estimations of resilience-related indicators, accounting for
failure events and interdependencies between EI and ICT. The outcome of these
analyses are especially helpful to understand the dynamics of relevant
phenomena and the reaction of critical components to them, so to provide
guidelines towards design improvements. Our modeling framework, from now on
called SG model, is based on Stochastic Activity Network (SAN) [5] formalism
and the analysis is performed via simulation so that domain specific
(probability) measures are obtained with statistical inference. Although at a
suitable level of abstraction to cope with the inherent complexity of the
modeling effort and related solution methods, the framework accounts for both
the EI and its ICT distribution control system, both at MV and LV level, to
properly capture the impact of dependencies among the system components. The
focus is on the analysis of accidental faults, malicious attacks and their
propagation through existing interdependencies. Notwithstanding the great
effort already invested in this modeling framework, the current implementation
still needs enhancements. Especially, the ability to address large grid
topologies is at the moment rather limited.

To this purpose, advancements in the adopted solutions would be greatly
beneficial, in terms of both structural approaches supporting the development
models and analytical solvers. This is the context where my PhD thesis intends
to provide contributions. In particular, two major aspects of our framework
that strongly impact on performance, and so the ability to tackle large grid
infrastructures, have been identified:

  * •

the model composition operator, at the basis of a modular modeling approach as
adopted in the framework,

  * •

the Power Flow Problem (PFP) solution strategy, essential for the electrical
grid state estimation.

Both definition of new model composition operator and PFP solution strategy
are considered in my proposal, and of course these are assumed as basic
starting points for the planned research investigations. Another category of
enhancements is new _scenarios_ and measures definition and analysis. In fact,
the main research line promoted by our lab at SEDC/̄ISTI is the development of
realistic scenarios of accidental failures or intentional attacks and the
analysis of their impact on control operations. In nowadays distribution EIs,
control strategies need to be tested upon dynamic environmental changes and
with respect to a gamut of measures (voltage quality, demand fulfillment,
power losses, propagation of blackouts, etc.), thus our framework has to be
continuously refined to address analysis of sophisticated grid configurations
and failure models.

Summing up, my PhD work is focused on three research lines: new scenarios
definition and analysis, new model composer strategies definitions and
implementation, and the study of PFP solution methods, as depicted in Figure
1.

Figure 1:  Research lines, dashed boxes, with respect to SG model. PFP and
Model composer have a direct impact on performance, while considering new
scenarios enlarges model complexity and consequently can have also an impact
on performance.

Structure of the paper: Section II presents interesting scenarios studied so
far, describing the effects of faults or attacks originating from EI or ICT
components; Section III briefly discusses three modeling choices we have
already tested on a more general case study with the aim to select the best
from the performance point of view; Section IV presents the PFP and discusses
investigation directions; in Section V conclusions are drawn and future work
is sketched out.

##  II Smart Grid scenarios definition and analysis

The focus is on the MV level, that is composed by the MV-EI and the Medium
Voltage Monitoring and Control System (MV-MCS). Considered complex control
policies pose our model in the so called SG scenario [6]. In the following the
name SG will refer to both EI and Monitoring and Control System (MCS)
together. From a modeling point of view, the MV-EI can be represented as a
radial or partially meshed graph, where:

  * •

an arc represents a power line with the associated switch, OLTC (transformer
having voltage regulator) and protection breakers, if any;

  * •

each node is structured like a Bus-Bar (BUS) with the associated electrical
equipment. Those considered in the proposed modeling framework are:

    * –

Distributed Generator (DG): Volatile small-scale energy generating unit,
producing electricity from, e.g., Renewable Energy System (RES) (such as wind,
hydro, solar or photovoltaic). It can offer flexibility in the power profile,
through power curtailment or re-dispatch.

    * –

Inflexible Load (IFL): Classic load for which a loss of power is a blackout.

    * –

Flexible Load (FL): Load that offers flexibility in the power profile.
Electrical charging stations can be considered an example of flexible load.

Thus, both integer and real state variables are employed in order to capture
the MV-EI dynamics in continuous time. In addition, the MV-EI state is
evaluated via the solution of a PFP. These aspects pose modeling challenges
and motivates the choice of SAN formalism.

As an example, consider the grid shown in Figure 2, taken from [7], that is
composed of $11$ BUSes, $10$ power lines, one OLTC between BUSes $B1$ and
$B2$, two DGs (photovoltaic at BUS $B4$ and wind at BUS $B11$), and five
loads, among which four are IFLs and one (_INDUSTRY_ at BUS $B3$) is FL.

Figure 2: Diagram of a MV smart grid from [7] (the communication layer is not
shown).

The MV-MCS is supposed to have a perfect knowledge of the MV-EI state and
control actions are performed after an optimization problem is solved. These
control actions pose modeling challenges that are addressed by our SG model
taking advantages in particular of SAN gates [7, 8].

One aspect that has been emphasized in conceiving the modeling framework is
the ability to account for a variety of failures, involving either the cyber
control, or the grid infrastructure, or both. At the moment, only the _effect_
on MV-MCS and MV-EI of failures are modeled, e.g., if the communication link
between the MV-MCS and the OLTC fails at a given time instant then the voltage
drop at the ends of the transformer is considered fixed from that moment on,
but details about how and why the link has failed are not modeled. Once a
failure occurs, its propagation inside the system is accounted for and the
resulting impact evaluated. The analyses progressed by first considering the
presence of individual failures, and then enlarging the failure events, to
also appreciate the effects of simultaneous combinations thereof. In this
paper, only failures affecting the cyber infrastructure responsible for the
distribution grid control are presented; specifically, three types of failure
have been considered in [7]:

  * •

timing malicious failure, modeled as delayed/omitted application of (part of)
the control actions;

  * •

control device failure, modeled as an incomplete application of the control
actions. Specifically, the failure of control devices local to the distributed
energy resources is tackled, leading to lack of control on the produced power
and unavailability to perform curtailment of production to assure energy
balancing;

  * •

OLTC failure, potentially resulting in unsuccessful voltage control since OLTC
constitutes a major device through which voltage regulation is performed.

We have also considered the LV part of the grid [8], studying different
failures, and in general the interaction between MV and LV, but in the
following only a MV case study is reported to demonstrate the potentialities
of our SG model.

The developed stochastic model-based analysis is suited to assess a variety of
measures of interest to final customers, service providers and system
operators. Given the interest in the voltage control functionality and its
ability to promote resilient grid operation through fulfillment of voltage
requirements, the following indicators have been evaluated:

  1. 1.

the voltage $V_{\\_}i(t)$ on bus $i$ measured at each time instant $t$ within
the considered analysis period;

  2. 2.

the probability that the value of $V_{\\_}i(t)$ on bus $i$ is out of bound of
the nominal voltage: either undervoltage $UV_{\\_}i(t)$ or overvoltage
$OV_{\\_}i(t)$;

  3. 3.

the probability $P^{\widetilde{MV1}}_{\\_}i$ that the $10$ min mean value of
the supply voltage must be within $10\%$ of the nominal voltage for $99\%$ of
the time, evaluated over a week is _not_ met on bus $i$ (in order to simplify
the analysis the requirement has been evaluated over the considered analysis
interval of $24$ hours);

  4. 4.

the average unsatisfied power demand $UD_{\\_}i(t)$ on load $i$ at each
instant of time $t$.

  5. 5.

the average curtailment of available power $CA_{\\_}i(t)$ on generator $i$ at
each instant of time $t$;

Metrics 2) and 3) are representative of the degree of reliability of the smart
grid in delivering its service, while metrics 4) and 5) express the
effectiveness of the analyzed voltage control functionality in satisfying
customers expectations. As an example, in Figure 3 measure 3), i.e., the
probability $P^{\widetilde{MV1}}_{\\_}i$ that the voltage requirement is not
met, is depicted for every BUS $i$ of the grid illustrated in Figure 2,
comparing the impact of timing failure with respect to failures of the control
device of Wind Power Plant (WP).

Figure 3: Probability $P^{\widetilde{MV1}}_{\\_}i$ that the grid voltage
requirement is not met, for all buses in the grid, for two different values of
timing failure (10 min and 20 min), when failures of the control device of WP
occur and when they do not occur.

In order to compute measures 2) and 3) with a reasonably small confidence
interval (e.g., $10^{-5}$) exercising grids of the size of Figure 2 or with
$48$ BUSes, as in [8], several hours of computation are needed on a Intel(R)
Core(TM) i7-5960X with fixed 3.50 GHz CPU, 20M cache and 32GB RAM, an up to
date GNU/Linux Operating System and using the Möbius Modeling Framework [9].
Being interested in addressing electrical grids with hundreds or thousands
BUSes, such as in the IEEE118, IEEE300 testbed [10, 11] and the Illinois
Center for a Smarter Electric Grid’s Texas synthetic grid [12], directions for
improvements are presented in Sections III and IV.

##  III New modeling strategies definition

Abstracting away from the SG scenario, the logical structure of the considered
systems comprises:

  * •

A large number of cyber/̄physical components, weakly interconnected with each
other according to physical and cyber topologies.

  * •

One or more generic components. Each generic component groups all the specific
components having common characteristics, i.e., homogeneous system components,
which, although different, share the same behaviour, structure and parameters.
This means that a template model built for the generic component is adequate
to represent the set of its specific components.

  * •

A central MCS capable to communicate with each specific component.

As examples of weakly interconnected electrical components, in the IEEE118,
IEEE300 testbed [10, 11] and the Illinois Center for a Smarter Electric Grid’s
Texas synthetic grid [12], the interconnection degrees are numbers between $2$
and $3$ on average, with maximum value of $16$ for the configuration with
$2000$ nodes. Electrical nodes are representable as instances of a generic
component, called BUS; different electrical components, e.g., DGs and OLTCs,
can be attached to each BUS, thus electrical nodes are identified by their
position in the electrical grid and the list of components attached on them.
In the rest of the paper, as an example of communication topology, we will
consider the MV-MCS connected directly to all the MV electrical components.

In order to describe how the system logical structure is translated in our SG
model, why the model can not scale at increasing the number of electrical
nodes and my proposal for a new strategy to overcome the problem, some
additional information concerning the modeling formalism and composition
operators are needed. As already mentioned in Section I, we opt for the SAN
formalism [5], a stochastic extension of Petri nets based on four primitives:
places, activities (transitions), input gates, and output gates. Primitive
data types of the programming language C++, like short, float, double,
including structures and arrays, are represented by special places, called
“extended places”. Input gates define both the enabling condition of an
activity and the marking changes occurring when the activity completes. The
output gates define the marking changes occurring when the activity completes,
but they are randomly chosen at completion of the activity from a probability
distribution function, defined by “cases” associated to the activity. The
modeler defines input and output gates writing chunks of C++ code, thus having
a great expression power. Composed models are obtained through two
compositional operators, based on the sharing of places [13]:

  * •

_Join_ , composes, i.e., brings together two or more (composed or atomic)
submodels. The expression

$M=\mathcal{J}\Big{(}\\{p_{\\_}{1},\dots,p_{\\_}{m}\\};\,SM_{\\_}{1},\dots,SM_{\\_}{n}\Big{)}$

means that a new model $M$ is created by the juxtaposition of submodels
$SM_{\\_}{1}$, …, $SM_{\\_}{n}$ and if the place
$p_{\\_}{j}\in\\{p_{\\_}{1},\dots,p_{\\_}{m}\\}$ appears in more then one
submodel then $p_{\\_}{j}$ will appear only once in $M$, maintaining all the
arcs that connect $p_{\\_}{j}$ to activities and gates.

  * •

_Rep_ , automatically constructs identical copies (replicas) of a (composed or
atomic) submodel. The expression

$M=\mathcal{R}_{\\_}{n}\Big{(}\\{p_{\\_}{1},\dots,p_{\\_}{m}\\};\,SM\Big{)}$

means that the submodel $SM$ is copied $n$ times and the places
$\\{p_{\\_}{1},\dots,p_{\\_}{m}\\}$ are all shared among all the replicas.

In [14], issues in modeling a large population of similar and weakly
interconnected components were introduced and _NARep_ served as starting point
for the following discussion. We have identified three different modeling
strategies that match the system logical structure. Starting from a model of
the generic cyber/̄physical component, these strategies guide the automatic
definition of $n$ specific components:

  * •

_State/̄Sharing_ (_SS_): the generic component model _GENCOMP_ comprises an
indexing mechanism, the index/̄dependent behaviour model and the set
$\\{s_{\\_}{1},\dots,s_{\\_}{n}\\}$ of places, where $s_{\\_}{j}$ describes
the portion of component $j$ state that is relevant for some other component.
_GENCOMP_ is replicated $n$ times and $\\{s_{\\_}{1},\dots,s_{\\_}{n}\\}$ is
globally accessible. Formally:

$\mathcal{R}_{\\_}{n}\Big{(}\\{s_{\\_}{1},\dots,s_{\\_}{n}\\};\,GENCOMP\Big{)}$

This strategy, already presented in [15], is momentary implemented in our SG
model [7]. It is a general solution, but its efficiency is limited by the fact
that it assumes a complete graph of interactions among the replicated
components. This assumption does not match with the great majority of
real/̄world systems, typically composed by many loosely interconnected
components according to regular dependency topologies (tree, mesh, cycle,
etc).

  * •

_Channel/̄Sharing_ (_CS_): the generic component model _GENCOMP_ comprises an
indexing mechanism, the index/̄dependent behaviour model, a communication
channel _ch_ and the submodel _CHMAN_ that manage the channel. Formally:

$\mathcal{R}_{\\_}{n}\Big{(}\\{ch\\};\,\mathcal{J}\Big{(}\\{ch\\};\,GENCOMP,CHMAN\Big{)}\Big{)}$

_GENCOMP_ is replicated $n$ times but only _ch_ , a light extended place, is
shared among all the replicas. _CHMAN_ regulates the channel usage and
maintains in sync, inside each replica, a copy of portion of other components’
state. Synchronizations take place by means of instantaneous actions, thus
dependability measures are not impacted by _CHMAN_ , but the price to pay is
the increase of the events number. Details about this strategy and comparisons
with _SS_ will appear in EPEW2017 workshop proceedings [16].

  * •

_Dependency/̄Aware Replication_ (_DARep_): the generic system component is
modeled by means of the template model _TEMPLATE_ and the interdependency
topology $\emph{T}_{n}$. Starting from _TEMPLATE_ and $\emph{T}_{n}$, $n$ new
models $COMP_{\\_}{1},\dots,COMP_{\\_}{n}$ are automatically created, where
$COMP_{\\_}{i}$ contains $s_{\\_}{j}$, a portion of component $j$ state, only
if component $i$ depends on component $j$. All the component models are joined
together, but each $s_{\\_}{j}$ is shared only among those models that need
it. Formally:

$\mathcal{J}\Big{(}\\{s_{\\_}{1},\dots,s_{\\_}{n}\\};\,COMP_{\\_}{1},\dots,COMP_{\\_}{n}\Big{)}$

A new composition operator that is capable to produce
$COMP_{\\_}{1},\dots,COMP_{\\_}{n}$ starting from _TEMPLATE_ and
$\emph{T}_{n}$ have been defined; its implementation, in conjunction with the
Möbius framework, is based on XQuery [17]. Details about this operator will
appear in ISSRE2017 conference proceedings [18].

All three approaches have been tested on a case study that is effective in
demonstrating the features of the mechanisms, and can be considered as a basis
to be easily extended and adapted to represent a great variety of real
contexts, far beyond the SG scenario. We have considered $n$ working stations
dedicated to perform the same task in parallel. At every time instant, each
station can be either _working_ or _failed_ , and the change of status takes
place after an exponentially distributed random time. The failure of a station
implies a reconfiguration of the workload assigned to the other stations, to
continue accomplishing the tasks of the failed station. Just before failing, a
station redirects its tasks to one or more other stations it is connected
with, i.e. neighbouring stations according to the dependency topology. The
stations that receive new tasks increase their workload, implying also a
change of their failure rate. Thus, the model is a pure death process [19]
with monotone load sharing [20].

We have modeled the case study following all the three strategies (_SS_, _CS_
and _DARep_) studying in particular how to transform the model that implements
_SS_ into models that implement _CS_ and _DARep_ in order to facilitate the
change of strategy inside our SG model. Performance comparisons have confirmed
the expected improvements. Results of a complete analysis will appear in [18],
and here, to illustrate the improvements, only time measures about _SS_ and
_DARep_, obtained with the terminating simulator of the Möbius tool [9], are
briefly discussed. In particular, consider $\Delta\tau(k)$ the difference
between the total amount of _CPU_ time, in seconds, used by one execution of
the Möbius simulator that runs $k$ batches and the amount of _CPU_ time, in
seconds, used by one execution of the Möbius simulator to initialize the data
structures of the simulator.

TABLE I: $\Delta\tau(1000)$ in seconds for the _SS_ approach.

$d=1$ $d=9$ $d=99$ $d=500$ $n=10^{1}$ $0.087$ $0.102$ $n=10^{2}$ $9.203$
$9.197$ $9.357$ $n=10^{3}$ $1613.246$ $1723.666$ $1732.983$ $1754.996$

TABLE II: $\Delta\tau(1000)$ in seconds for the _DARep_ approach.

$d=1$ $d=9$ $d=99$ $d=500$ $n=10^{1}$ $0.0015$ $0.0022$ $n=10^{2}$ $0.774$
$0.817$ $0.972$ $n=10^{3}$ $104.939$ $109.797$ $131.580$ $167.160$

Tables I and II depict $\Delta\tau^{\acs{SS}}(k)$ and
$\Delta\tau^{\acs{RO}}(k)$ respectively, where $k=1000$ simulation batches are
considered for a variable number $n$ of system components, each being
dependent on a variable number $d$ of other components.

Although the values shown by _DARep_ are very small and significantly lower
than the corresponding ones of _SS_, it can be observed the different trend of
the two approaches with respect to $d$. In fact, while the impact of $d$ on
$\Delta\tau(1000)$ is very small in the table relative to _SS_, in the case of
_DARep_ the value of $\Delta\tau(1000)$ for $d=500$ is about $1.6$ the value
for $d=1$. This is not surprising, since _SS_ always works under the implicit
assumption of maximum interconnection among component replicas, so its
sensitivity to variation of $d$ is minimal, while _DARep_ is influenced by
$d$, given the applied principle of considering only real replicas
interdependencies. With respect to increasing values of $n$, as expected the
results obtained for $\Delta\tau(1000)$ increase for both approaches. However,
_DARep_ can be about one order of magnitude faster than _SS_ when $n=1000$ and
$d$ up to $9$.

##  IV Power Flow Problem solution improvements

In our SG model, the EI state is determined [21] from the knowledge, for all
BUS $i$, of:

  * •

injected power phasor $S^{g}_{\\_}{i}$,

  * •

demanded power phasor $S^{d}_{\\_}{i}$,

  * •

lines characteristics (admittance bus matrix $Y_{\\_}{bus}$),

  * •

relationship between power $S^{bus}_{\\_}{i}$ and voltage $V_{\\_}{i}$ given
by

$S^{bus}_{\\_}{i}=V_{\\_}{i}\sum_{\\_}{k}^{n}\big{(}Y^{*}_{\\_}{bus}\big{)}_{\\_}{ik}V^{*}_{\\_}{k}\text{,}$

  * •

power balance equations

$G_{\\_}{i}(V_{\\_}{1},\dots,V_{\\_}{n})=S^{bus}_{\\_}{i}+S^{d}_{\\_}{i}-S^{g}_{\\_}{i}=0\text{.}$

The PFP consists in extracting relevant information from the equations
$G(V)=0$. Notice that $S^{g}_{\\_}{i}$ is the sum of powers produced by DGs
attached at BUS $i$ and $S^{d}_{\\_}{i}$ is the sum of powers consumed by
loads attached at BUS $i$. Thus, during the simulation of the stochastic
process described by our SG model, each new event, e.g. failure of a DG, can
induce different values of power generated/requested and then a new PFP has to
be solved. The most common strategy to solve the PFP consists in breaking up
the complex set of non/̄linear equations $G(V)=0$ in real and imaginary parts,
and in considering the polar decomposition of voltages in order to obtain the
real set $F=0$ of $2n$ non/̄linear equations. The Newton/̄Raphson method [21]
is adopted to solve $F=0$ but its standard formulation is inefficient and
constitutes a relevant bottleneck during the SG model simulation.

To mitigate the impact of this computation, the Inexact/̄Newton/̄Krylov GMRES
method [22] have been proposed and implemented so that a gain in scalability
with respect to the number $n$ of BUSes is expected. The INK GMRES is impacted
by the equations ordering, as preliminary discussed in [23], and particular
choices of orderings can result in even better performance. Another strategy,
originating from [24], to solve the PFP requires the introduction of a new
complex parameter $s$ and the analysis of the set of _functional_ equations
$\tilde{G}(V(s))=0$. This strategy, still to be detailed, is a promising
alternative to the Newton/̄Raphson method in the SG scenario because, with
adequate adjustments, can handle many similar PFPs with a single computation,
with benefits in therms of computational cost over the entire model
simulation.

##  V Conclusions

Moving from considerations on the need to promote efficient dependability and
performability model/̄based analysis to properly address the increasing size
of modern and future SGs, this paper presented three research lines I am
addressing in the context of my PhD studies. New SG scenarios definition with
high interaction between ICT and EI, and increasing level of details, is the
main topic of my research. It presents modeling challenges from the
performance point of view and then addresses new modeling strategies and new
EI state representation via advanced PFP solution strategies. The main idea of
new modeling solutions, _CS_ and _DARep_, is to exploit the actually existing
dependencies among components of the system under analysis, instead of relying
on the pessimistic situation of point/̄to/̄point connections as assumed by the
already existing _SS_ approach. The main idea of PFP solution improvements is
to re/think the Newton/̄Raphson method and to study the applicability of its
alternatives.

Extensions of the presented studies are foreseen in several directions, some
of which are:

  * •

new scenarios definition, in particular, introducing the interaction between
HV and MV by means of a limited power interchange between them and new
measures about the quality of service perceived not only by the electrical
service provider but also by consumers,

  * •

tackle source of failure, not addressed at the moment,

  * •

re/̄design our SG model to include the _DARep_ approach and test it on large
SGs,

  * •

study different orderings of the equations arising from the PFP to increase
the model simulation performance,

  * •

study the feasibility of new PFP solution techniques, such as elaborations on
$\tilde{G}=0$, application in the SG scenario,

  * •

apply the _DARep_ approach in modeling system outside the SG scenario,

  * •

a long term objective would be to define and making native in the adopted
evaluation tool a new non/̄anonymous replica operator, based on the principle
of _DARep_.

## Acknowledgment

I would like to thank Felicita Di Giandomenico, my advisor, and Silvano
Chiaradonna for providing insights and expertise that are guiding my research.

## References

  * [1] A. Avizienis, J.-C. Laprie, B. Randell, and C. Landwehr, “Basic concepts and taxonomy of dependable and secure computing,” _IEEE Trans. Depend. Sec. Comput._ , vol. 1, no. 1, pp. 11–33, 2004.
  * [2] R. Zeng, Y. Jiang, C. Lin, and X. Shen, “A stochastic petri nets approach to dependability analysis of control center networks in smart grid,” in _2011 International Conference on Wireless Communications and Signal Processing (WCSP)_ , Nov 2011, pp. 1–5.
  * [3] D. S. Menasché, R. M. Meri Leäo, E. de Souza e Silva, A. Avritzer, S. Suresh, K. Trivedi, R. A. Marie, L. Happe, and A. Koziolek, “Survivability analysis of power distribution in smart grids with active and reactive power modeling,” _SIGMETRICS Perform. Eval. Rev._ , vol. 40, no. 3, pp. 53–57, Jan. 2012.
  * [4] J. S. A. Carneiro and L. Ferrarini, “Reliability analysis of power system based on generalized stochastic petri nets,” in _Proceedings of the 10th International Conference on Probablistic Methods Applied to Power Systems_ , May 2008, pp. 1–6.
  * [5] W. H. Sanders and J. F. Meyer, “Stochastic activity networks: Formal definitions and concepts,” in _Lectures on formal methods and performance analysis: first EEF/Euro summer school on trends in computer science, Berg en Dal, The Netherlands, July 3-7, 2000, Revised Lectures_ , ser. LNCS, E. Brinksma, H. Hermanns, and J. P. Katoen, Eds. Springer-Verlag, 2001, vol. 2090, pp. 315–343.
  * [6] T. S. G. I. P. C. S. W. Group, “Guidelines for smart grid cyber security: Vol. 3, supportive analyses and references,” National Institute of Standards and Technology, NISTIR 7628, August 2010.
  * [7] S. Chiaradonna, F. Di Giandomenico, and G. Masetti, “Analyzing the impact of failures in the electric power distribution grid,” in _Seventh Latin-American Symp. on Dependable Comput. (LADC)_ , Cali, Colombia, Oct. 2016\.
  * [8] ——, “A stochastic modelling framework to analyze smart grids control strategies,” in _Fourth IEEE International Conf. on Smart Energy Grid Eng. (SEGE 2016)_ , Oshawa, Canada, Aug. 2016.
  * [9] D. D. Deavours, G. Clark, T. Courtney, D. Daly, S. Derisavi, J. M. Doyle, W. H. Sanders, and P. G. Webster, “The Möbius framework and its implementation,” _IEEE Trans. on Software Engineering_ , vol. 28, no. 10, pp. 956–969, 2002.
  * [10] R. Christie, “IEEE 118-bus test case,” http://icseg.iti.illinois.edu/ieee-118-bus-system, 1993.
  * [11] M. Adibi and IEEE Test Systems Task Force, “IEEE 300-bus test case,” http://icseg.iti.illinois.edu/ieee-300-bus-system, 1993.
  * [12] Illinois Center for a Smarter Electric Grid (ICSEG), “June 2016 texas 2000 syntetic test case,” http://icseg.iti.illinois.edu/synthetic-power-cases/texas2000-june2016, 2016\.
  * [13] W. H. Sanders and J. F. Meyer, “A unified approach for specifying measures of performance, dependability and performability,” in _Dependable Computing for Critical Applications, Vol. 4 of Dependable Computing and Fault-Tolerant Systems_ , A. Avizienis and J. Laprie, Eds. Springer Verlag, 1991, pp. 215–237.
  * [14] S. Chiaradonna, F. Di Giandomenico, and G. Masetti, “Efficient non-anonymous composition operator for modeling complex dependable systems,” _CoRR_ , vol. abs/1608.05874, 2016. [Online]. Available: http://arxiv.org/abs/1608.05874
  * [15] F. Flammini, _Critical Infrastructure Security: Assessment, Prevention, Detection, Response_ , ser. Information & communication technologies. WIT Press, 2012.
  * [16] G. Masetti, S. Chiaradonna, and F. Di Giandomenico, “Stochastic dependability analysis of large systems through an efficient modeling approach dealing with non-anonymous entities,” forthcoming IEEE 28th International Symposium on Software Reliability Engineering (ISSRE), Toulouse, France, Oct. 2017.
  * [17] M. Brundage, _XQuery: The XML Query Language_. Pearson Higher Education, 2004.
  * [18] G. Masetti, S. Chiaradonna, and F. Di Giandomenico, “Model-based simulation in mobius: an efficient approach targeting loosely interconnected components,” forthcoming Computer Performance Engineering: 13th European Workshop (EPEW), Berlin, Germany, Sep. 2017.
  * [19] K. S. Trivedi, _Probability and Statistics with Reliability, Queuing and Computer Science Applications_ , 2nd ed. Chichester, UK: John Wiley and Sons Ltd., 2002.
  * [20] B. M. Amari, _Handbook of Performability Engineering_. Springer, 2008.
  * [21] D. L. R. Idema, _Computational Methods in Power System Analysis_ , ser. Atlantis Studies in Scientific Computing in Electromagnetics. Springer, 2014.
  * [22] R. Idema, D. J. P. Lahaye, C. Vuik, and L. van der Sluis, “Scalable newton-krylov solver for very large power flow problems,” _IEEE Transactions on Power Systems_ , vol. 27, no. 1, pp. 390–396, Feb 2012.
  * [23] G. Masetti, S. Chiaradonna, and F. Di Giandomenico, “Exploring equations ordering influence on variants of the newton-raphson method,” in _Numerical Computations: Theory and Algorithms_ , Y. Sergeyev, Ed. AIP Conference Proceedings, 2016.
  * [24] A. Trias, “The holomorphic embedding load flow method,” in _Power and Energy Society General Meeting, 2012 IEEE_ , July 2012, pp. 1–8.

  *[$MF$]: malicious failure state
  *[$MFF$]: malicious failure free state
  *[SAN]: Stochastic Activity Network
  *[LC]: Logical Controller
  *[AN]: Access Network
  *[LVGC]: Low Voltage Grid Control
  *[LV-EI]: Low Voltage Electric Infrastructure
  *[LV_EI_M]: Composed model representing LV-EI
  *[LV_MCS_M]: Composed model representing LV-MCS
  *[PL]: Power Line
  *[MV-EI]: Medium Voltage Electric Infrastructure
  *[DS]: Distributed Storage unit
  *[OLTC]: On Load Tap Changer
  *[WAN]: Wide Area Network
  *[CMCS]: Central Management and Control System
  *[INTERNET]: Internet network
  *[CSYS]: Central System
  *[CMCSWAN]: Wide Area Network associated to
  *[MV_MCS_M]: Composed model representing MV-MCS
  *[MV_EI_M]: Composed model representing MV-EI
  *[MVGC]: Medium Voltage Grid Control
  *[HV]: High Voltage
  *[MV]: Medium Voltage
  *[LV]: Low Voltage
  *[ICT]: Information and Communications Technologies
  *[EI]: Electrical Infrastructure
  *[SG]: Smart Grid
  *[PFP]: Power Flow Problem
  *[EIs]: Electrical Infrastructure
  *[MV-MCS]: Medium Voltage Monitoring and Control System
  *[MCS]: Monitoring and Control System
  *[BUS]: Bus-Bar
  *[DG]: Distributed Generator
  *[RES]: Renewable Energy System
  *[IFL]: Inflexible Load
  *[FL]: Flexible Load
  *[BUSes]: Bus-Bar
  *[DGs]: Distributed Generator
  *[IFLs]: Inflexible Load
  *[$V_{\\_}i(t)$]: voltage on bus i at time t
  *[WP]: Wind Power Plant
  *[OLTCs]: On Load Tap Changer
  *[_SS_]: State/̄Sharing
  *[_CS_]: Channel/̄Sharing
  *[_DARep_]: Dependency/̄Aware Replication
  *[PFPs]: Power Flow Problem
  *[SGs]: Smart Grid


Given an $(r + 1)$-chromatic graph $H$, the fundamental edge stability result of Erdős and Simonovits says that all $n$-vertex $H$-free graphs have at most $(1 - 1/r + o(1)) \binom{n}{2}$ edges, and any $H$-free graph with that many edges can be made $r$-partite by deleting $o(n^{2})$ edges.

Here we consider a natural variant of this – the minimum degree stability of $H$-free graphs. In particular, what is the least $c$ such that any $n$-vertex $H$-free graph with minimum degree greater than $cn$ can be made $r$-partite by deleting $o(n^{2})$ edges? We determine this least value for all 3-chromatic $H$ and for very many non-3-colourable $H$ (all those in which one is commonly interested) as well as bounding it for the remainder. This extends the Andrásfai-Erdős-Sós theorem and work of Alon and Sudakov.

§ INTRODUCTION

A central theme in extremal graph theory is the structure of graphs which do not contain some fixed subgraph $H$. Some of the oldest questions in the area are what is the greatest number of edges such a graph can have, what is the structure of these extremal graphs and how stable is this structure. The classical result is that of Erdős and Simonovits.

Fix a graph $H$ with chromatic number $r + 1$. If $G$ is an $H$-free graph with $n$ vertices, then $e(G) \leqslant (1 - 1/r + o(1)) \binom{n}{2}$. Furthermore, if $G$ has $(1 - 1/r + o(1)) \binom{n}{2}$ edges, then $G$ can be obtained from the $r$-partite Turán graph, $T_{r}(n)$, by deleting and adding $o(n^{2})$ edges.

In particular, all $H$-free graphs with close to the extremal number of edges are close to $(\chi(H) - 1)$-partite. In place of the number of edges, it is natural to consider the structure of $H$-free graphs with large minimum degree and whether they are close to $(\chi(H) - 1)$-partite. In 1974, Andrásfai, Erdős and Sós [4] did this when $H$ is an $(r + 1)$-clique. Their seminal result was the following.

Let $r \geqslant 2$ and $G$ be a $K_{r + 1}$-free graph with $n$ vertices and minimum degree greater than

\begin{equation*}
\biggl(1 - \frac{1}{r - 1/3}\biggr) n.
\end{equation*}

Then $G$ is $r$-colourable. Furthermore $1 - 1/(r - 1/3)$ is tight.

Note that the $K_{r + 1}$-free graph with greatest minimum degree (and most edges), the Turán graph, $T_{r}(n)$, has minimum degree $(1 - 1/r)n$ so the theorem gives information about graphs whose minimum degrees are $\Omega(n)$ away from that of the extremal graph – we are far from the regime of <Ref>.

We now consider <Ref> from the perspective of minimum degree stability. The graph consisting of a 5-cycle joined to a complete $(r - 2)$-partite graph with 3 vertices in each part shows that $1 - 1/(r - 1/3)$ is tight. Furthermore, balanced blow-ups (defined in <Ref>) of this graph  show that there are $n$-vertex $K_{r + 1}$-free graphs with minimum degree $(1 - 1/(r - 1/3)) n$ which require the removal of at least $\Omega(n^{2})$ edges to be made $r$-partite. This suggests the most basic problem for the minimum degree stability of $H$-free graphs: given a $(r + 1)$-chromatic graph $H$, we wish to determine

\begin{equation*}
\begin{split}
\delta_{H} = \inf \{c : \ &\textrm{if }\ssize{G} = n, \, \delta(G) \geqslant c n \textrm{ and } G \textrm{ is } H\textrm{-free}, \\
& \textrm{then } G \textrm{ can be made } r\textrm{-partite by deleting } o(n^{2}) \textrm{ edges}\}.
\end{split}
\end{equation*}

The reason for allowing the omission of $o(n^{2})$ edges is that there are many $H$ for which the $H$-free graph with greatest minimum degree is not $r$-partite (but of course is very close to $r$-partite: it is close to the Turán graph). As a simple example, let $H = K_{r + 1}(2)$ be the complete $(r + 1)$-partite graph with two vertices in each part. The $r$-partite Turán graph together with a complete matching inside each part is $H$-free and so the $H$-free graph with greatest minimum degree has minimum degree greater than $n(1 - 1/r)$ and hence is not $r$-partite.

It follows from our previous discussion that

\begin{equation*}
\delta_{K_{r + 1}} = 1 - \frac{1}{r - 1/3}.
\end{equation*}

As pointed out by Alon and Sudakov [3], a standard application of Szemerédi's regularity lemma [20] shows that

\begin{equation*}
\delta_{K_{r + 1}(t)} = 1 - \frac{1}{r - 1/3},
\end{equation*}

where $K_{r + 1}(t)$ is the complete $(r + 1)$-partite graph with $t$ vertices in each part (so is a Turán graph). [In [3] a stronger version of this statement is proved, with sharper estimates on the number of edges that need deleting, and Allen [1] found a more direct proof yielding the optimal estimates.] Given the role played by $K_{r + 1}(t)$ in edge stability, it might be tempting to believe that this equation should determine $\delta_{H}$ for general non-bipartite $H$. Indeed, if $H$ is a graph with chromatic number $\chi(H) = r + 1 \geqslant 3$, then $H$ is a subgraph of $K_{r + 1}(t)$ for some $t$ and so any $H$-free graph is $K_{r + 1}(t)$-free. Thus,

\begin{equation}
\delta_{H} \leqslant \delta_{K_{r + 1}(t)} = 1 - \frac{1}{r - 1/3}.\label{eq:AS}
\end{equation}

However, the inequality may be strict. In the case of edge stability, the Turán graph, $T_{r}(n)$, has $(1 - 1/r) \binom{n}{2}$ edges and does not contain $H$, as $H$ has chromatic number $r + 1$. Here, however, it is blow-ups of $K_{r - 2} + C_{5}$ (mentioned above) which show that $\delta_{K_{r + 1}(t)} \geqslant 1 - 1/(r - 1/3)$. These are $K_{r + 1}$-free, but need not be $H$-free – for a simple example, consider $r = 2$ and $H$ an odd cycle. Minimum-degree stability is more nuanced: $\delta_{H}$ is determined not just by the chromatic number of $H$ but also by its finer structural properties. For 3-chromatic graphs, the situation is fairly simple.

[$\delta_{H}$ for 3-chromatic $H$]theoremdeltaHthree
Let $H$ be a 3-chromatic graph. There is a smallest positive integer $g$ such that $H$ is not homomorphic to $C_{2g + 1}$. Then

\begin{equation*}
\delta_{H} = \frac{2}{2g + 1}.
\end{equation*}

Next we turn to graphs which are not 3-colourable. We will determine $\delta_{H}$ for very many $H$ (indeed, all that one is commonly interested in) and bound it for the remainder. The graphs $H_{2}^{+}$, $T_{0}$, etc. mentioned in the theorem will be discussed in <Ref> and shown in <Ref> – for now it suffices to say that they are all 4-chromatic.

[$\delta_{H}$ for $H$ not 3-colourable]theoremdeltaHfour
We define a sequence of graphs $F_{g}$ $(1 \leqslant g \leqslant 12)$ and constants $c_{g}$ $(1 \leqslant g \leqslant 11)$ as follows.

$g$     1     2     3     4     5     6     7     8     9     10     11     12

$F_{g}$     $K_{4}$     $W_{5}$     $W_{7}$     $\overline{C}_{7}$     $W_{9}$     $H_{2}^{+}$     $W_{11}$     $H_{2}$     $W_{13}$     $T_{0}$     $W_{15}$     $H_{1}^{++}$

$c_{g}$     $\frac{2}{3}$     $\frac{2}{5}$     $\frac{1}{3}$     $\frac{2}{7}$     $\frac{1}{4}$     $\frac{2}{9}$     $\frac{1}{5}$     $\frac{2}{11}$     $\frac{1}{6}$     $\frac{2}{13}$     $\frac{1}{7}$

Let $r \geqslant 3$ be an integer. If $H$ is a $(r + 1)$-chromatic graph and $g + 1$ is minimal such that $H$ is not homomorphic to $K_{r - 3} + F_{g + 1}$, then

\begin{equation*}
\delta_{H} = 1 - \frac{1}{r - 1 + c_{g}}.
\end{equation*}

If $H$ is homomorphic to all $K_{r - 3} + F_{g}$ $(1 \leqslant g \leqslant 12)$, then there is a smallest positive integer $g$ for which $H$ is not homomorphic to $K_{r - 2} + C_{2g + 1}$: $\delta_{H}$ satisfies the bounds

\begin{equation*}
1 - \frac{1}{r - 1} < 1 - \frac{1}{r - 1 + 2/(2g - 1)} \leqslant \delta_{H} \leqslant 1 - \frac{1}{r - 1 + 1/7}.
\end{equation*}

The sequence of graphs $F_{g}$ is slightly unusual. Firstly the graphs do not increase in size. Secondly it is not always true that $F_{g + 1}$ is homomorphic to $F_{g}$ and so it is, for example, possible for a graph to be homomorphic to both $F_{3}$ and $F_{5}$ but not $F_{4}$. The only graphs whose $\delta_{H}$ value is not determined by <Ref> are those which are homomorphic to all the $K_{r - 3} + F_{g}$. Such a graph would be rare.

§.§ Wider context

We give a second view of $\delta_{H}$, placing it within a whole spectrum of structural constants relating to $H$-free graphs. The chromatic profile of a graph $H$ is the sequence of values for $k = 1, 2, \dotsc$ of

\begin{equation*}
\delta_{\chi}(H, k) = \inf\set{c : \text{if }\delta(G) \geqslant c \ssize{G} \text{ and } G \text{ is } H\text{-free}, \text{then } G \text{ is $k$-colourable}}.
\end{equation*}

The question of determining this was first asked by Erdős and Simonovits [11] in 1973. The Andrásfai-Erdős-Sós theorem says exactly that $\delta_{\chi}(K_{r + 1}, r) = 1 - 1/(r - 1/3)$. The chromatic profile of triangles has been studied extensively [4, 5, 7, 13, 15, 17, 21] and was finally settled by Brandt and Thomassé [6]. These results were extended to general cliques [12, 18].

Much less is known about the chromatic profile of non-complete graphs (Erdős and Simonovits described the behaviour as “too complicated”). For many $H$, the exact structure and chromatic number of even the $H$-free graphs with most edges (let alone highest minimum degree) is unknown. Of course, we do know that any such graph is very close to a Turán graph. For these reasons it is natural to consider an approximate chromatic profile

\begin{equation*}
\begin{split}
\delta^{\ast}_{\chi}(H, k) = \inf \{c : \ &\textrm{if }\ssize{G} = n, \, \delta(G) \geqslant c n \text{ and } G \textrm{ is } H\textrm{-free}, \\
& \textrm{then } G \textrm{ can be made } k\textrm{-colourable by deleting } o(n^{2}) \textrm{ edges}\}.
\end{split}
\end{equation*}

If $H$ is $(r + 1)$-chromatic, then the $r$-partite Turán graph, $T_{r}(n)$ is $H$-free and cannot be made $(r - 1)$-colourable without deleting $\Omega(n^{2})$ edges. Also, any $n$-vertex $H$-free graph has at most $(1 - 1/r + o(1))\binom{n}{2}$ edges and so has minimum degree at most $(1 - 1/r + o(1)) n$. Thus, for all $k \leqslant r - 1$ we have $\delta^{\ast}_{\chi}(H, k) = 1 - 1/r$. In particular, the first interesting threshold in the approximate chromatic profile of $H$ is

\begin{equation*}
\delta^{\ast}_{\chi}(H, \chi(H) - 1)
\end{equation*}

which is exactly $\delta_{H}$.

This approximate chromatic profile is related to another very natural chromatic profile. Define

\begin{equation*}
\begin{split}
\delta_{\chi}(H\text{-hom}, k) = \inf\{c : \ &\text{if }\delta(G) \geqslant c \ssize{G} \text{ and } H \textrm{ is not homomorphic to } G, \\
& \text{then } G \text{ is $k$-colourable}\},
\end{split}
\end{equation*}

as the chromatic profile of the family of $H$-homomorphism-free graphs. In <Ref> we will show that this is identical to approximate chromatic profile of $H$ and so $\delta_{H} = \delta_{\chi}(H\text{-hom}, \chi(H) - 1)$.

For any graph $H$ and any positive integer $k$,

\begin{equation*}
\delta^{\ast}_{\chi}(H, k) = \delta_{\chi}(H\text{\emph{-hom}}, k).
\end{equation*}

§.§ The graphs in <Ref>

Various graphs appear in the statement of <Ref>. The graph $W_{k}$ (called a $k$-wheel) is a single vertex joined to a $k$-cycle – $W_{7}$ is displayed below. The graph $\overline{C}_{7}$ is the complement (and also the square) of a 7-cycle. The graph $H_{2}$ is obtained from $\overline{C}_{7}$ by deleting an edge (while maintaining 4-chromaticness) and $H_{2}^{+}$ is obtained from $H_{2}$ by adding a vertex of degree three. The graph $H_{1}^{++}$ can be obtained from $H_{2}$ by deleting an edge and adding two degree three vertices. Finally, $T_{0}$ is a 7-cycle (the outer cycle) together with two vertices each joined to six of the seven vertices in the outer cycle (with the `seventh' vertices two apart) as well as a vertex of degree three.

in 0,1,...,6

(*360/7 + 90:1)v_

in 0,1,...,6

in 0,1,...,6

(*360/7 + 90:1)v_

*$C_{7}^{2} = \overline{C}_{7}$

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
(u,v_0 u,v_2 u,v_5)

in 0,1,...,6

(*360/7 + 90:1)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)

in 0,1,...,6

(*360/7 + 90:1)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

in 0,1,...,6

(*360/7 + 90:1)v_

(ul,v_0 ul,v_2 ul,v_3 ur,v_0 ur,v_5 ur,v_3)

To prove <Ref>, we will need the following result, which appears in [14], and again makes reference to the graphs in <Ref>. A graph is $a$-locally bipartite if the common neighbourhood of every $a$-clique is bipartite. A graph is locally bipartite if it is $1$-locally bipartite: every neighbourhood in the graph is bipartite. Note that a graph is locally bipartite exactly if it does not contain an odd wheel. The graphs appearing in <Ref> are either odd wheels or locally bipartite.

Let $G$ be an $a$-locally bipartite graph.

* If $\delta(G) > (1 - 1/(a + 4/3)) \cdot \ssize{G}$, then $G$ is $(a + 2)$-colourable.

* If $\delta(G) > (1 - 1/(a + 5/4)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + \overline{C}_{7}$.

* If $\delta(G) > (1 - 1/(a + 6/5)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + \overline{C}_{7}$ or $K_{a - 1} + H_{2}^{+}$.

* If $\delta(G) > (1 - 1/(a + 7/6)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + H_{2}$.

* If $\delta(G) > (1 - 1/(a + 8/7)) \cdot \ssize{G}$, then $G$ is either $(a + 2)$-colourable or contains $K_{a - 1} + H_{2}$ or $K_{a - 1} + T_{0}$.

§.§ Notation

Given a graph $G$, a blow-up of $G$, is a graph obtained by replacing each vertex $v$ of $G$ by a non-empty independent set $I_{v}$ and each edge $uv$ by a complete bipartite graph between classes $I_{u}$ and $I_{v}$. We say we have blown-up a vertex $v$ by $n$ if $\ssize{I_{v}} = n$. It is often helpful to think of this as weighting vertex $v$ by $n$.

A blow-up is balanced if the independent sets $(I_{v})_{v \in G}$ are as equal in size as possible. We use $G(t)$ to denote the graph obtained by blowing-up each vertex of $G$ by $t$, i.e. $G(t)$ is the balanced blow-up of $G$ on $t \ssize{G}$ vertices. For example, the balanced blow-up of the $r$-clique, $K_{r}$, on $n$ vertices is exactly the Turán graph, $T_{r}(n)$. We note in passing that a graph has the same chromatic and clique number as any of its blow-ups. Furthermore if $H$ is a blow-up of $G$, then $G$ is $a$-locally bipartite if and only if $H$ is.

Given two graphs $G$ and $H$, the join of $G$ and $H$, denoted by $G + H$, is the graph obtained by taking disjoint copies of $G$ and $H$ and joining each vertex of the copy of $G$ to each vertex of the copy of $H$. Note that the chromatic and clique numbers of $G + H$ are the sum of the chromatic and clique numbers of $G$ and $H$.

A graph $G$ is homomorphic to a graph $H$, written $G \rightarrow H$, if there is a map $\varphi : V(G) \rightarrow V(H)$ such that for any edge $uv$ of $G$, $\varphi(u)\varphi(v)$ is an edge of $H$. A graph $G$ is homomorphic to a graph $H$ if and only if $G$ is a subgraph of some blow-up of $H$. In particular, if $G \rightarrow H$, then $\chi(G) \leqslant \chi(H)$ and moreover if $H$ is $a$-locally bipartite, then $G$ is also.

§.§ Tools

We will make great use of Szemerédi's regularity lemma [20] together with some associated machinery which we describe here. Let $(X, Y)$ be a pair of vertex subsets of graph $G$. We use $d(X, Y) = e(X, Y) \ssize{X}^{-1} \ssize{Y}^{-1}$ to denote the density between $X$ and $Y$. The pair $(X, Y)$ is $\varepsilon$-regular if

\begin{equation*}
\abs{d(U, V) - d(X, Y)} \leqslant \varepsilon
\end{equation*}

for all $U \subset X$, $V \subset Y$ with $\ssize{U} \geqslant \varepsilon \ssize{X}$ and $\ssize{V} \geqslant \varepsilon \ssize{Y}$. A partition $\sca{P} = V_{0} \cup V_{1} \cup \dotsb \cup V_{k}$ of $V(G)$ is an $\varepsilon$-regular partition if:

* $V_{1}$, $V_{2}$, …, $V_{k}$ all have equal size and $\ssize{V_{0}} \leqslant \varepsilon \ssize{G}$,

* For all but at most $\varepsilon \binom{k}{2}$ pairs $ij$ ($i < j$), the pair $(V_{i}, V_{j})$ is $\varepsilon$-regular.

Szemerédi's celebrated result is that, for every positive integer $\ell$ and $\varepsilon > 0$, there is some $L = L(\ell, \varepsilon)$ such that every graph with at least $\ell$ vertices has an $\varepsilon$-regular partition into at least $\ell$ but at most $L$ parts. We will need a version of Szemerédi's regularity lemma which works well with minimum degrees.

Fix $\varepsilon > 0$ and some $\lambda \geqslant 0$. Suppose we have a graph $G$ with some $\varepsilon$-regular partition $\sca{P} = V_{0} \cup V_{1} \cup \dotsb \cup V_{k}$. These induce what is called a reduced graph $R(\sca{P}, \varepsilon, \lambda)$: this has vertex set $[k] = \set{1, 2, \dotsc, k}$ with vertex $i$ joined to vertex $j$ exactly if the pair $(V_{i}, V_{j})$ is $\varepsilon$-regular and $d(V_{i}, V_{j}) \geqslant \lambda$. Note when $\lambda = 0$ this graph will have at least $(1 - \varepsilon) \binom{k}{2}$ edges by the definition of an $\varepsilon$-regular partition. We will make use of the following version of the regularity lemma which is an immediate corollary of Theorem 1.10 in Komlós and Simonovits's survey of the subject [16].

Let $\varepsilon > 0$, $\lambda, \delta \in [0, 1]$ and $\ell$ be a positive integer. There is a positive integer $L$ such that the following holds for all $n \geqslant \ell$. If $G$ is graph on $n$ vertices with $\delta(G) \geqslant \delta n$, then $G$ has some $\varepsilon$-regular partition $\sca{P} = V_{0} \cup V_{1} \cup \dotsb \cup V_{k}$ with $k$ between $\ell$ and $L$ such that the corresponding reduced graph $R(\sca{P}, \varepsilon, \lambda)$ has minimum degree at least $(\delta - \varepsilon - \lambda) k$.

The point of the reduced graph is that if it contains some structure, then we can find a large structure in $G$, by using a building lemma (for example, see Theorem 2.1 in [16]).

Let $H$ be a graph (on vertex set $\set{1, 2, \dotsc, \ssize{H}}$), $t$ a positive integer and $\lambda \in (0, 1)$. For all sufficiently small $\varepsilon > 0$ the following holds. Suppose $V_{1}$, …, $V_{\ssize{H}}$ are sufficiently large pairwise disjoint vertex sets with $(V_{i}, V_{j})$ $\varepsilon$-regular of density at least $\lambda$ for each $ij \in E(H)$. Then we can find a copy of $H(t)$ with each blown-up vertex in the corresponding $V_{i}$.

These two lemmata work well together: given a large graph $G$ with minimum degree $\delta \ssize{G}$, <Ref> shows that $G$ has a corresponding reduced graph $R$ of bounded size and with minimum degree almost $\delta \ssize{R}$. If $G$ is $H(t)$-free, then, by <Ref>, $R$ is $H$-free. This may give some structural information about $R$ (e.g. it is $r$-colourable) which we will then pull back to $G$.

Finally, odd cycles will play an important role in determining $\delta_{H}$, so we note the following fact about homomorphisms to odd cycles.

Let $g$ be a positive integer. If $G$ is homomorphic to $C_{2g + 1}$, then $G$ contains no odd cycles of length less than $2g + 1$.

Let $\varphi$ be a homomorphism from $G$ to $C_{2g + 1}$. Let $C$ be an odd cycle of $G$. The restriction of $\varphi$ to $C$ gives a homomorphism from $C$ to $\varphi(C)$, so $\chi(\varphi(C)) \geqslant \chi(C) = 3$. Thus, $\varphi(C)$ is the whole of $C_{2g + 1}$, so $\ssize{C} \geqslant \ssize{\varphi(C)} = 2g + 1$.

§ $\DELTA_{H}$ FOR 3-CHROMATIC $H$ – PROOF OF <REF>

Let $H$ be a graph with chromatic number three, so $H$ is homomorphic to $K_{3} \cong C_{3}$. Furthermore, $H$ is not bipartite, so contains at least one odd cycle. This, coupled with <Ref>, means that $H$ is homomorphic to only finitely many odd cycles. Let $g$ be the smallest positive integer with $H$ not homomorphic to $C_{2g + 1}$. A balanced blow-up of $C_{2g + 1}$ on $n$ vertices is $H$-free and has minimum degree at least $2 \lfloor n/(2g + 1) \rfloor$. We claim that to make this balanced blow-up bipartite requires the deletion of at least $\lfloor n/(2g + 1) \rfloor^{2} = \Omega(n^{2})$ edges. Indeed, let the sizes of the $(2g + 1)$ parts in the blow-up be $\lceil n/(2g + 1) \rceil = x_{1} \geqslant x_{2} \geqslant \dotsb \geqslant x_{2g + 1} = \lfloor n/(2g + 1) \rfloor$. Then the number of copies of $C_{2g + 1}$ in the blow-up is $x_{1}x_{2} \dotsm x_{2g + 1}$ and each edge lies in at most $x_{1} x_{2} \dotsm x_{2g - 1}$ copies of $C_{2g + 1}$, so to make the blow-up bipartite requires the deletion of at least $x_{2g} x_{2g + 1} \geqslant \lfloor n/(2g + 1) \rfloor^{2}$ edges. In particular,

\begin{equation*}
\delta_{H} \geqslant \frac{2}{2g + 1}.
\end{equation*}

We claim that in fact there is equality. Before proving this, we need the following Andrásfai-Erdős-Sós style result for odd cycles, which was noted by Häggkvist [13]. For completeness we give a proof.

Let $g \geqslant 2$ be a positive integer. Suppose $G$ is a non-bipartite graph with

\begin{equation*}
\delta(G) > \frac{2}{2g + 1} \cdot \ssize{G}.
\end{equation*}

Then $G$ contains an odd cycle of length less than $2g + 1$.

Let $C$ be the shortest odd cycle in $G$. By minimality, $C$ is induced and no vertex is adjacent to three vertices in $C$. Thus,

\begin{equation*}
\ssize{C} \cdot \delta(G) \leqslant e(C, G) \leqslant 2 \ssize{G},
\end{equation*}

and so $\ssize{C} \leqslant 2 \ssize{G}/\delta(G) < 2g + 1$.

We are now ready to prove <Ref> which determines $\delta_{H}$ for 3-chromatic $H$.

The graph $H$ is not bipartite so contains an odd cycle. In particular, if $g$ is such that $2g + 1$ is greater than the length of the shortest odd cycle of $H$, then, by <Ref>, $H$ is not homomorphic to $C_{2g + 1}$. Take $g$ minimal with $H$ not homomorphic to $C_{2g + 1}$.

By the opening remarks of this section, a balanced blow-up of $C_{2g + 1}$ on $n$ vertices is $H$-free, with minimum degree at least $2\floor{n/(2g + 1)}$ and requires at least $\Omega_{g}(n^{2})$ edges to be deleted to be made bipartite so $\delta_{H} \geqslant 2/(2g + 1)$.

We are left to show that, for all $\eta > 0$, any $n$-vertex $H$-free graph with minimum degree at least

\begin{equation*}
\biggl(\frac{2}{2g + 1} + \eta\biggr)n,
\end{equation*}

can be made bipartite by deleting at most $\eta n^{2}$ edges when $n$ is sufficiently large. Firstly, note that $H$ is homomorphic to all of $C_{3}$, $C_{5}$, …, $C_{2g - 1}$, so there exists some positive integer $t$ such that $H$ is a subgraph of all of $C_{3}(t)$, $C_{5}(t)$, …, $C_{2g - 1}(t)$.

Fix $n$ and $\ell$ large (chosen later), let $\lambda = \eta /2$ and $\varepsilon > 0$ be sufficiently small. Let $G$ be a $n$-vertex graph with minimum degree at least $(2/(2g + 1) + \eta)n$. By <Ref>, $G$ has some $\varepsilon$-regular partition $\sca{P} = V_{0} \cup V_{1} \cup \dotsb \cup V_{k}$ with $k$ between $\ell$ and $L$ (a constant not depending on $G$ or $n$) such that the reduced graph $R = R(\sca{P}, \varepsilon, \lambda)$ has minimum degree greater than $2k/(2g + 1)$. By <Ref>, $R$ is either bipartite or contains one of $C_{3}$, $C_{5}$, …, $C_{2g - 1}$.

Applying <Ref>, provided $\varepsilon$ was chosen small enough (in terms of $\lambda$) and $n$ is large enough, either $R$ is bipartite or $G$ contains one of $C_{3}(t)$, $C_{5}(t)$, …, $C_{2g - 1}(t)$. The latter contradicts $G$ being $H$-free and so $R$ is bipartite.

Now, consider deleting from $G$ all edges within each $V_{i}$, the edges incident to $V_{0}$ and all edges between $V_{i}$ and $V_{j}$ when $ij \not\in E(R)$. The resulting graph is a blow-up of $R$, so is bipartite. This process deletes at most

\begin{align*}
& k \cdot (n/k)^{2} + \varepsilon n \cdot n + \varepsilon \tbinom{k}{2} (n/k)^{2} + \lambda n^{2} \\
\leqslant & \ n^{2}(\lambda + 2\varepsilon + 1/k) \\
\leqslant & \ n^{2}(\eta/2 + 2 \varepsilon + 1/\ell) \leqslant \eta n^{2}
\end{align*}

edges, provided that $\ell$ is large enough and $\varepsilon$ is small enough.

By <Ref>, the odd girth of $G$ is at least $2g - 1$ (where $g$ is as in the theorem statement). However, we may not have equality. For example, the Petersen graph has odd girth 5 but is not homomorphic to $C_{5}$, so $\delta_{\text{Petersen}}$ is $2/5$ and not $2/7$.

§ PROPERTIES OF $\DELTA_{H}$

We take a moment to crystallise the key ingredients of the proof of <Ref> (and, in particular, what role the odd cycles played). Fix $r \geqslant 2$ and suppose we have a sequence of graphs $K_{r + 1} = L_{1}, L_{2}, L_{3}, \dotsc, L_{m}$ and a sequence of constants $k_{1}, k_{2}, \dotsc, k_{m - 1}$ where $m$ may be infinity (if both sequences are infinite). The relevant properties this pair of sequences might satisfy are:

* None of $L_{1}, L_{2}$, $L_{3}$, … is $r$-colourable,

* No $(r + 1)$-chromatic graph is homomorphic to all of $L_{1}$, $L_{2}$, …,

* If $G$ is an $n$-vertex graph with minimum degree greater than $k_{g} n$, then $G$ is either $r$-colourable or contains at least one of $L_{1}$, $L_{2}$, …, $L_{g}$,

* For each $g$ and any $c < k_{g}$ there is some blow-up $L_{g + 1}'$ of $L_{g + 1}$ satisfying $\delta(L_{g + 1}') \geqslant c \cdot \lvert L_{g + 1}' \rvert$.

<Ref> corresponds to the sequences $L_{g} = C_{2g + 1}$ and $k_{g} = 2/(2g + 3)$ satisfying all the properties for $r = 2$. As odd cycles are regular we did not make use of the blow-ups in Property 4. However, the $L_{g + 1}$ we use later will often be non-regular and furthermore they may have no blow-ups with $\delta(L_{g + 1}') = k_{g} \cdot \lvert L_{g + 1}' \rvert$, but still satisfy Property 4. One could weaken Property 3 to minimum degree greater than $(k_{g} + o(1)) n$ (which is all we use in our analysis below) but for our purposes this is unnecessary.

Let $H$ be an $(r + 1)$-chromatic graph. Suppose $H$ is not homomorphic to $L_{g + 1}$ and Properties 1 and 4 hold. Then, for any $c < k_{g}$, let $G$ be a balanced blow-up of $L_{g + 1}'$ on $n$ vertices: $H$ is not homomorphic to $L_{g + 1}$, so $G$ is $H$-free. Furthermore, $G$ has minimum degree at least $\delta(L_{g + 1}') \lfloor n/ \lvert L_{g + 1}' \rvert \rfloor \geqslant c \lvert L_{g + 1}' \rvert \lfloor n/ \lvert L_{g + 1}' \rvert \rfloor$. Let the sizes of the $\lvert L_{g + 1}' \rvert$ parts of $G$ be $\lceil n/\lvert L_{g + 1}' \rvert \rceil \geqslant x_{1} \geqslant x_{2} \geqslant \dotsb \geqslant x_{\lvert L_{g + 1}' \rvert} \geqslant \lfloor n/\lvert L_{g + 1}' \rvert \rfloor$. Now, $G$ contains at least $x_{1}x_{2} \dotsm x_{\lvert L_{g + 1}' \rvert}$ copies of $L_{g + 1}'$ in which each vertex is in the corresponding part, and each edge of $G$ is in at most $x_{1}x_{2} \dotsm x_{\lvert L_{g + 1}' \rvert - 2}$ such copies. By Property 1, $L_{g + 1}$ and so $L_{g + 1}'$ are not $r$-colourable and hence to make $G$ $r$-colourable requires the deletion of at least $x_{\lvert L_{g + 1}' \rvert - 1} \cdot x_{\lvert L_{g + 1}' \rvert} \geqslant \lfloor n/\lvert L_{g + 1}' \rvert \rfloor^{2} = \Omega(n^{2})$ edges. Thus $\delta_{H} \geqslant c$ and so $\delta_{H} \geqslant k_{g}$.

Suppose $H$ is homomorphic to all of $L_{1}$, $L_{2}$, …, $L_{g}$ and Property 3 holds. Then the same regularity argument as in the proof of <Ref> shows that $\delta_{H} \leqslant k_{g}$. We now sketch the argument. Let $\eta > 0$ and take a large graph $G$ with minimum degree at least $(k_{g} + \eta) \ssize{G}$. We can use <Ref> to get a corresponding reduced graph $R$ with minimum degree greater than $(k_{g} + \eta')\ssize{R}$ (some $\eta' \in (0, \eta)$), which, by Property 3, is either $r$-colourable or contains one of $L_{1}$, $L_{2}$, …, $L_{g}$. In the latter case, we use <Ref> to get a copy of $H$ in $G$ and in the former case we may delete at most $\eta \ssize{G}^{2}$ edges from $G$ to leave an $r$-colourable graph.

The upshot of all this is that if Properties 1, 3 and 4 hold, then either $\delta_{H} \leqslant k_{m - 1}$ (if $H$ is homomorphic to all of $L_{1}$, $L_{2}$, …, $L_{m}$) or $\delta_{H} = k_{g}$ where $g$ is minimal with $H$ not homomorphic to $L_{g + 1}$. Of course, if Property 2 also holds, then we can determine $\delta_{H}$ for any $(r + 1)$-chromatic $H$. Even without Property 2, any sequence does determine $\delta_{H}$ for many $H$ and gives an upper bound for the rest. Thus, we are particularly interested in pairs of sequences satisfying Properties 1, 3 and 4.

We illustrate these remarks by next proving a weak version of <Ref>. Note that, when $r = 2$, $\delta_{H}$ could be arbitrarily close to zero (corresponding to $k_{g} \rightarrow 0$ as $g \rightarrow 0$). However, this is not the case for larger $r$.

If $H$ is a graph with chromatic number $r + 1 \geqslant 3$, then there is a least $g$ such that $H$ is not homomorphic to $K_{r - 2} + C_{2g + 1}$ and furthermore

\begin{equation*}
1 - \frac{1}{r - 1} < 1 - \frac{1}{r - 1 + 2/(2g - 1)} \leqslant \delta_{H} \leqslant 1 - \frac{1}{r - 1/3}.
\end{equation*}

The right-hand inequality is just inequality (<ref>). For the middle inequality define the following sequence of graphs: $L_{g} = K_{r - 2} + C_{2g + 1}$ (so $L_{1} = K_{r + 1}$) and let

\begin{equation*}
k_{g} = 1 - \frac{1}{r - 1 + 2/(2g + 1)}.
\end{equation*}

From the preceding discussion it suffices to show that these sequences satisfy Properties 1, 2 and 4 (but not necessarily 3). In particular, if $g$ is minimal such that $H$ is not homomorphic to $L_{g}$, then

\begin{equation*}
\delta_{H} \geqslant k_{g - 1} > 1 - \frac{1}{r - 1}.
\end{equation*}

Property 1 is immediate: each $L_{g}$ has chromatic number $\chi(K_{r - 2}) + \chi(C_{2g - 1}) = r - 2 + 3 = r + 1$.

Suppose $H$ is some $(r + 1)$-chromatic graph which is homomorphic to all the $L_{g}$ and let the homomorphisms be $\varphi_{g} : H \rightarrow L_{g} = K_{r - 2} + C_{2g + 1}$. Now $\varphi_{g}^{-1}(K_{r - 2})$ is $(r - 2)$-colourable, so $X_{g} = \varphi_{g}^{-1}(C_{2g + 1})$ is not bipartite (as $H$ is not $r$-colourable). In particular, for each $g$, $H[X_{g}]$ is not bipartite but $H[X_{g}] \rightarrow C_{2g + 1}$. Thus, by <Ref>, $H[X_{g}]$ contains an odd cycle of length at least $2g + 1$. Therefore, $H$ contains odd cycles of arbitrary length, which is absurd. Hence, we have Property 2.

Finally, for Property 4, let $L_{g}' = K_{r - 2}(2g - 1) + C_{2g + 1}$, which is a blow-up of $L_{g}$. The graph $L_{g}'$ has $(2g - 1)(r - 2) + 2g + 1 = (2g - 1)(r - 1) + 2$ vertices and is $[(2g - 1)(r - 2) + 2]$-regular. In particular,

\begin{equation*}
k_{g - 1} \cdot \lvert L_{g}' \rvert = \biggl(1 - \frac{2 g - 1}{(r - 1)(2g - 1) + 2}\biggr) \cdot [(2g - 1)(r - 1) + 2] = \delta(L_{g}'). \qedhere
\end{equation*}

§ $\DELTA_{H}$ FOR GENERAL $H$ – PROOF OF <REF>

We are now ready to use our results on $a$-locally bipartite graph to prove <Ref>, which we state again here for convenience.

The lower bound

\begin{equation*}
1 - \frac{1}{r - 1 + 2/(2g - 1)} \leqslant \delta_{H}
\end{equation*}

in the final part of the theorem follows from <Ref>. The discussion following Properties 1 to 4 shows that what remains is to check that the sequences

\begin{equation*}
L_{g} = K_{r - 3} + F_{g}, \qquad k_{g} = 1 - \frac{1}{r - 1 + c_{g}}
\end{equation*}

satisfy Properties 1, 3 and 4. Property 1 is immediate: for each $g$, $\chi(L_{g}) = r - 3 + \chi(F_{g}) = r + 1$.

We now consider Property 4. When $F_{g + 1} = W_{2k + 1}$, $c_{g} = 2/(2k - 1)$. For $L_{g + 1} = K_{r - 3} + W_{2k + 1} = K_{r - 2} + C_{2k + 1}$, we take $L_{g + 1}' = K_{r - 2}(2k - 1) + C_{2k + 1}$. This is a regular blow-up of $L_{g + 1}$ and, as was shown in the proof of <Ref>, satisfies

\begin{equation*}
\biggl(1 - \frac{1}{r - 1 + c_{g}}\biggr) \cdot \lvert L_{g + 1}' \rvert = \delta(L_{g + 1}'),
\end{equation*}

which is exactly $k_{g} \cdot \lvert L_{g + 1}' \rvert = \delta(L_{g + 1}')$. When $F_{g + 1} = \overline{C}_{7}$ (i.e. $g = 3$), $c_{g} = 1/3$. We take $L_{g + 1}' = K_{r - 3}(3) + \overline{C}_{7}$ which is a regular blow-up of $L_{g + 1}$. This satisfies

\begin{equation*}
\delta(L_{g + 1}') \lvert L_{g + 1}' \rvert^{-1} = \frac{3r - 5}{3r - 2} = 1 - \frac{1}{r - 1 + 1/3} = k_{g}.
\end{equation*}

This establishes Property 4 except for $g = 5, 7, 9, 11$. <Ref> shows the weightings (which induce blow-ups) of $F_{g + 1}$ we would like to use (they maximise the minimum degree relative to the order). However, some care will be needed owing to the zero weights. Consider the case $g = 5$. <Ref> shows a 9-vertex weighted graph with minimum degree 5, however, owing to the zero weights, this is not strictly a blow-up of $F_{6} = H_{2}^{+}$. But for any $c < 5/9$ there is a genuine blow-up, $H_{2}^{+\prime}$, of $H_{2}^{+}$ with $\delta(H_{2}^{+\prime}) \geqslant c \cdot \lvert H_{2}^{+\prime} \rvert$.

Let $c < k_{5}$: $c = 1 - 1/(r - 1 + \beta)$ for some $\beta < c_{5} = 1/4$ and so $k = 1 - 1/(2 + \beta) < 5/9$. Let $H_{2}^{+\prime}$ be a blow-up of $H_{2}^{+}$ satisfying $\delta(H_{2}^{+\prime}) \geqslant k \cdot \lvert H_{2}^{+\prime} \rvert$. Let $L_{6}' = K_{r - 3}(\lvert H_{2}^{+\prime} \rvert - \delta(H_{2}^{+\prime})) + H_{2}^{+\prime}$ which is a blow-up of $L_{6}$. This satisfies

\begin{align*}
\delta(L_{6}') \lvert L_{6}' \rvert^{-1} & = \frac{(r - 3)\lvert H_{2}^{+\prime} \rvert - (r - 4) \delta(H_{2}^{+\prime})}{(r - 2) \lvert H_{2}^{+\prime} \rvert - (r - 3) \delta(H_{2}^{+\prime})} \\
& = 1 - \frac{\lvert H_{2}^{+\prime} \rvert - \delta(H_{2}^{+\prime})}{(r - 2) \lvert H_{2}^{+\prime} \rvert - (r - 3) \delta(H_{2}^{+\prime})} \\
& = 1 - \frac{1}{r - 3 + 1/(1 - \delta(H_{2}^{+\prime}) \lvert H_{2}^{+\prime} \rvert^{-1})} \\
& \geqslant 1 - \frac{1}{r - 3 + 1/(1 - k)} \\
& = 1 - \frac{1}{r - 3 + 2 + \beta} = c,
\end{align*}

which establishes Property 4 for $g = 5$. Similar calculations hold for $g = 7, 9, 11$ (for $g = 7$, there are even no troublesome zero weights). Indeed, for $c < k_{g}$: $c = 1 - 1/(r - 1 + \beta)$ for some $\beta < c_{g}$ and so $k = 1 - 1/(2 + \beta)$ is less than 6/11 (for $g = 7$), less than 7/13 (for $g = 9$) and less than 8/15 (for $g = 11$). <Ref> shows that there is a blow up $F_{g + 1}'$ of $F_{g + 1}$ with $\delta(F_{g + 1}') \geqslant k \cdot \lvert F_{g + 1}' \rvert$. Then $L_{g + 1}' = K_{r - 3}(\lvert F_{g + 1}' \rvert - \delta(F_{g + 1}')) + F_{g + 1}'$ is a blow-up of $L_{g + 1}$, which satisfies $\delta(L_{g + 1}') \lvert L_{g + 1}' \rvert^{-1} \geqslant c$. Thus the sequences satisfy Property 4.

in 0,1,...,6

(*360/7 + 90:1.5)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)
(u,v_0 u,v_2 u,v_5)

$H_{2}^{+}$ weighted

in 0,1,...,6

(*360/7 + 90:1.5)v_

(v_1,v_3,v_5,v_0, v_2,v_4,v_6)

$H_{2}$ weighted

in 0,1,...,6

(*360/7 + 90:1.5)v_

(t,v_0 t,u_1 t,u_6)
in 0,2,3,4,5,6

in 0,1,2,3,4,5

[below right = -3pt](u_1)3
[below left = -3pt](u_6)3

$T_{0}$ weighted

in 0,1,...,6

(*360/7 + 90:1.5)v_

(ul,v_0 ul,v_2 ul,v_3 ur,v_0 ur,v_5 ur,v_3)

$H_{1}^{++}$ weighted

We are left to show that the sequences satisfy Property 3. We will make extensive use of the results about $a$-locally bipartite graphs given in <Ref>. Let $G$ be a graph with minimum degree greater than $k_{g} \cdot \ssize{G}$.

First suppose that $G$ is not $(r - 2)$-locally bipartite. Then there is an $(r - 2)$-clique $K$ in $G$ whose common neighbourhood is not bipartite. Let $G_{K}$ be the induced subgraph of $G$ whose vertex set is the common neighbourhood of the vertices in $K$. Let the vertices of $K$ be $x_{1}, x_{2}, \dotsc, x_{r - 2}$. Note that for each $v \in V(G)$,

\begin{equation*}
\mathds{1}(v \in G_{K}) \geqslant \mathds{1}(vx_{1} \in E(G)) + \dotsb + \mathds{1}(vx_{r - 2} \in E(G)) - (r - 3)
\end{equation*}

and so summing over all the vertices gives

\begin{equation*}
\lvert G_{K} \rvert \geqslant (r - 2) \delta(G) - (r - 3) \ssize{G} > \bigl((r - 2) k_{g} - (r - 3)\bigr) \cdot \ssize{G}.
\end{equation*}

Note that $\delta(G_{K}) \geqslant \delta(G) - (\ssize{G} - \ssize{G_{K}}) = \ssize{G_{K}} - (\ssize{G} - \delta(G))$ so

\begin{align*}
\frac{\delta(G_{K})}{\ssize{G_{K}}} & \geqslant 1 - \frac{\ssize{G} - \delta(G)}{\ssize{G}} \cdot \frac{\ssize{G}}{\ssize{G_{K}}} > 1 - \biggl(1 - \frac{\delta(G)}{\ssize{G}}\biggr) \cdot \frac{1}{(r - 2) k_{g} - (r - 3)} \\
& > 1 - \frac{1 - k_{g}}{(r - 2) k_{g} - (r - 3)} = 1 - \frac{1}{1 + c_{g}}.
\end{align*}

For $g = 1$: $G_{K}$ is not bipartite and $\delta(G_{K}) > 2/5 \cdot \ssize{G_{K}}$ so, by <Ref>, $G_{K}$ contains a triangle and so $G$ contains a $K_{r - 2} + K_{3} = K_{r - 3} + F_{1}$. Similarly for $g = 2$, $G$ contains one of $K_{r - 3} + F_{1}$ and $K_{r - 3} + F_{2}$ and for $g = 3$, $G$ contains one of $K_{r - 3} + F_{1}$, $K_{r - 3} + F_{2}$ and $K_{r - 3} + F_{3}$. More generally, for $g$ even, $G$ contains $K_{r - 3} + F_{\ell}$ for some $\ell \in \set{1, 2, 3, 5, \dotsc, g - 1}$ and for $g$ odd, $G$ contains $K_{r - 3} + F_{\ell}$ for some $\ell \in \set{1, 2, 3, 5, \dotsc, g}$.

Now suppose that $G$ is $(r - 2)$-locally bipartite. For $g = 1, 2, 3$:

\begin{equation*}
\delta(G)\ssize{G}^{-1} > 1 - \frac{1}{r - 1 + c_{3}} = 1 - \frac{1}{r - 2 + 4/3},
\end{equation*}

so, by <Ref>, $G$ is $r$-colourable. For $g = 4, 5$:

\begin{equation*}
\delta(G)\ssize{G}^{-1} > 1 - \frac{1}{r - 1 + c_{5}} = 1 - \frac{1}{r - 2 + 5/4},
\end{equation*}

so, by <Ref>, $G$ is $r$-colourable or contains $K_{r - 3} + \overline{C}_{7} = L_{4}$. For $g = 6, 7$:

\begin{equation*}
\delta(G)\ssize{G}^{-1} > 1 - \frac{1}{r - 1 + c_{7}} = 1 - \frac{1}{r - 2 + 6/5},
\end{equation*}

so, by <Ref>, $G$ is $r$-colourable or contains $K_{r - 3} + \overline{C}_{7} = L_{4}$ or contains $K_{r - 3} + H_{2}^{+} = L_{6}$. For $g = 8, 9$:

\begin{equation*}
\delta(G)\ssize{G}^{-1} > 1 - \frac{1}{r - 1 + c_{9}} = 1 - \frac{1}{r - 2 + 7/6},
\end{equation*}

so, by <Ref>, $G$ is $r$-colourable or contains $K_{r - 3} + H_{2} = L_{8}$. Finally, for $g = 10, 11$:

\begin{equation*}
\delta(G)\ssize{G}^{-1} > 1 - \frac{1}{r - 1 + c_{11}} = 1 - \frac{1}{r - 2 + 8/7},
\end{equation*}

so, by <Ref>, $G$ is $r$-colourable or contains $K_{r - 3} + H_{2} = L_{8}$ or contains $K_{r - 3} + T_{0} = L_{10}$. Hence, the sequences do indeed satisfy Property 3, as required.

§ APPROXIMATE CHROMATIC PROFILE AND HOMOMORPHISM-FREE GRAPHS

In <Ref> we introduced two chromatic profiles related to $\delta_{H}$. The first was the approximate chromatic profile of $H$,

\begin{equation*}
\begin{split}
\delta^{\ast}_{\chi}(H, k) = \inf \{c : \ &\textrm{if }\ssize{G} = n, \delta(G) \geqslant c n, G \textrm{ is } H\textrm{-free}, \\
& \textrm{then } G \textrm{ can be made } k\textrm{-colourable by deleting } o(n^{2}) \textrm{ edges}\},
\end{split}
\end{equation*}

and the second was the chromatic profile of the family of $H$-homomorphism-free graphs,

\begin{equation*}
\delta_{\chi}(H\text{-hom}, k) = \inf\set{c : \text{if }\delta(G) \geqslant c \ssize{G} \text{ and } H \nrightarrow G, \text{then } G \text{ is $k$-colourable}},
\end{equation*}

We now prove <Ref> which says that these are one and the same.

We first show that $\delta^{\ast}_{\chi}(H, k) \geqslant \delta_{\chi}(H\text{-hom}, k)$. Let $c < \delta_{\chi}(H\text{-hom}, k)$, so there is a non-$k$-colourable graph $G$ with minimum degree at least $c \ssize{G}$ and to which $H$ is not homomorphic. Let $G'$ be a balanced blow-up of $G$ on $n$ vertices: $H$ is not homomorphic to $G$, so $G'$ is $H$-free. Furthermore, $G'$ has minimum degree at least $c \ssize{G} \lfloor n/\ssize{G} \rfloor$. Just as in <Ref>, it is easy to check by counting copies of $G$ that to make $G'$ $k$-colourable requires the deletion of $\Omega(n^{2})$ edges. In particular, $\delta^{\ast}_{\chi}(H, k) \geqslant c$, as required.

We now show that $\delta^{\ast}_{\chi}(H, k) \leqslant \delta_{\chi}(H\text{-hom}, k)$. Let $\gamma > 0$, $c = \delta_{\chi}(H\text{-hom}, k) + 2\gamma$ and let $G$ be an $n$-vertex $H$-free graph with $\delta(G) \geqslant c n$. Let

\begin{equation*}
\sca{H} = \{H' : H \rightarrow H', \lvert H' \rvert \leqslant \ssize{H}\},
\end{equation*}

and note that this is finite and that $H$ is homomorphic to a graph if and only if that graph contains some $H' \in \sca{H}$. There is some $t \leqslant \ssize{H}$ such that $H \subset H'(t)$ for every $H' \in \sca{H}$.

Fix $H' \in \sca{H}$. The graph $G$ is $H$-free so does not contain $H'(t)$. By Erdős's result on the extremal function for complete $\ell$-uniform $\ell$-partite hypergraphs [8], $G$ must contain $o(n^{\ssize{H'}})$ copies of $H'$ (for more details see <cit.>). By the graph removal lemma (see for example <cit.>), $G$ can be made $H'$-free by deleting $o(n^{2})$ edges. As $\sca{H}$ is finite, there is a spanning subgraph $G'$ of $G$ with $e(G) - e(G') = o(n^{2})$ which contains no $H' \in \sca{H}$.

Take $G'$ and sequentially delete vertices of degree less than $(c - \gamma)n$ until no more remain. Provided $n$ is large enough, so that $(e(G) - e(G'))/n^{2}$ is sufficiently small, this process will terminate with the deletion of at most $o(n)$ vertices. Let the resulting graph be $G''$. Then $G''$ satisfies $\delta(G'') \geqslant (c - \gamma) \ssize{G''}$ and $G''$ contains no $H' \in \sca{H}$. In particular, $H$ is not homomorphic to $G''$. But $c - \gamma > \delta_{\chi}(H\text{-hom}, k)$ so $G''$ is $k$-colourable. Furthermore $G''$ was obtained from $G$ by the deletion of $o(n^{2})$ edges. Thus $\delta^{\ast}_{\chi}(H, k) \leqslant c$, as required.

§ ACKNOWLEDGEMENT

I would like to thank Andrew Thomason for many helpful discussions.

[1]
P. Allen.
Dense $H$-free graphs are almost $(\chi(H)-1)$-partite.
Electronic Journal of Combinatorics, 17(1):Research Paper 21,
1–11, 2010.

[2]
P. Allen, J. Böttcher, S. Griffiths, Y. Kohayakawa, and R. Morris.
Chromatic thresholds in dense random graphs.
Random Structures & Algorithms, 51(2):185–214, 2017.

[3]
N. Alon and B. Sudakov.
$H$-free graphs of large minimum degree.
Electronic Journal of Combinatorics, 13(1):Research Paper 19,
1–9, 2006.

[4]
B. Andrásfai, P. Erdős, and V. T. Sós.
On the connection between chromatic number, maximal clique and
minimal degree of a graph.
Discrete Mathematics, 8(3):205–218, 1974.

[5]
S. Brandt.
On the structure of dense triangle-free graphs.
Combinatorics, Probability and Computing, 8(3):237–245, 1999.

[6]
S. Brandt and S. Thomassé.
Dense triangle-free graphs are four-colorable: a solution to the
Erdős-Simonovits problem, 2005.
Submitted. Available at
<http://perso.ens-lyon.fr/stephan.thomasse/> .

[7]
C. C. Chen, G. P. Jin, and K. M. Koh.
Triangle-free graphs with large degree.
Combinatorics, Probability and Computing, 6(4):381–396, 1997.

[8]
P. Erdős.
On extremal problems of graphs and generalized graphs.
Israel Journal of Mathematics, 2(3):183–190, Sep 1964.

[9]
P. Erdős.
Some recent results on extremal problems in graph theory.
In Theory of Graphs (International Symposium, Rome,
1966), pages 117–123. Gordon and Breach, New York; Dunod, Paris, 1967.

[10]
P. Erdős.
On some new inequalities concerning extremal properties of graphs.
In Theory of Graphs (Proceedings of Colloquium, Tihany,
1966), pages 77–81. Academic Press, New York, 1968.

[11]
P. Erdős and M. Simonovits.
On a valence problem in extremal graph theory.
Discrete Mathematics, 5(4):323–334, 1973.

[12]
W. Goddard and J. Lyle.
Dense graphs with small clique number.
Journal of Graph Theory, 66(4):319–331, 2011.

[13]
R. Häggkvist.
Odd cycles of specified length in nonbipartite graphs.
Annals of Discrete Mathematics, 13:89–99, 1982.

[14]
F. Illingworth.
The chromatic profile of locally colourable graphs, Feb 2021.
Submitted. Available at <https://arxiv.org/abs/2102.05522> .

[15]
G. P. Jin.
Triangle-free four-chromatic graphs.
Discrete Mathematics, 145(1):151–170, 1995.

[16]
J. Komlós and M. Simonovits.
Szemerédi's regularity lemma and its applications in graph
In Combinatorics, Paul Erdős is eighty, Vol. 2
(Keszthely, 1993), volume 2 of Bolyai Society Mathematical Studies,
pages 295–352. János Bolyai Mathematical Society, Budapest, 1996.

[17]
T. Łuczak.
On the structure of triangle-free graphs of large minimum degree.
Combinatorica, 26(4):489–493, Aug 2006.

[18]
V. Nikiforov.
Chromatic number and mimimum degree of ${K}_{r}$-free graphs, Jan
Available at <https://arxiv.org/abs/1001.2070> .

[19]
M. Simonovits.
A method for solving extremal problems in graph theory, stability
In Theory of Graphs (Proceedings of Colloquium, Tihany,
1966), pages 279–319. Academic Press, New York, 1968.

[20]
E. Szemerédi.
Regular partitions of graphs.
In Problèmes combinatoires et théorie des graphes
(Colloquium International CNRS, University Orsay, Orsay, 1976),
volume 260 of Colloquium International CNRS, pages 399–401. CNRS,
Paris, 1978.

[21]
C. Thomassen.
On the chromatic number of triangle-free graphs of large minimum
Combinatorica, 22(4):591–596, Oct 2002.