Siyuan Niu
email: siyuan.niu@lirmm.fr

Aida Todri-Sanial

Effects of Dynamical Decoupling and Pulse-level Optimizations on IBM Quantum Computers

Currently available quantum computers are prone to errors. Circuit optimization and error mitigation methods are needed to design quantum circuits to achieve better fidelity when executed on NISQ hardware. Dynamical decoupling (DD) is generally used to suppress the decoherence error and different DD strategies have been proposed. Moreover, the circuit fidelity can be improved by pulse-level optimization, such as creating hardware-native pulse-efficient gates. This paper implements all the popular DD sequences and evaluates their performances on IBM quantum chips with different characteristics for various well-known quantum applications. Also, we investigate combining DD with pulse-level optimization method and apply them to QAOA to solve Max-Cut problem. Based on the experimental results, we found that DD can be a benefit for only certain types of quantum algorithms, while the combination of DD and pulse-level optimization methods always has a positive impact. Finally, we provide several guidelines for users to learn how to use these noise mitigation methods to build circuits for quantum applications with high fidelity on IBM quantum computers.

I. INTRODUCTION

Quantum computing is rapidly growing in recent years and various technologies have been developed for different quantum platforms, the leading candidates being superconducting and trapped-ion devices. Several companies such as IBM, Rigetti, and IonQ provide publicly available cloud-based services which allow users to access their platforms remotely. But, today's quantum computers are still prone to errors caused by either unavoidable interactions with the environment or imperfect quantum controls. They are qualified as Noisy Intermediate-Scale Quantum (NISQ) computers [START_REF] Preskill | Quantum computing in the nisq era and beyond[END_REF]. The largest quantum chip to date has 127 qubits released by IBM [START_REF]IBM quantum unveiled eagle, a 127-qubit quantum processor[END_REF]. Quantum error correction (QEC) has been proposed to eliminate the noise impact and help achieve a fault-tolerant quantum device [START_REF] Calderbank | Quantum error correction via codes over gf (4)[END_REF][START_REF]Quantum error correction for quantum memories[END_REF]. However, the implementation of quantum error correction codes requires a large number of ancilla qubits, which is not feasible on current hardware. Therefore, alternative approaches are needed to tackle the noise issue.

In order to reduce the noise impact and improve the quantum circuit fidelity, several quantum software were designed and they have made a great contribution to different circuit design processes, such as circuit synthesis [START_REF] Matteo | Parallelizing quantum circuit synthesis[END_REF][START_REF] Zhang | Optimal quantum circuit synthesis from controlled-unitary gates[END_REF], or qubit mapping [START_REF] Niu | A hardware-aware heuristic for the qubit mapping problem in the nisq era[END_REF][START_REF] Li | Tackling the qubit mapping problem for nisq-era quantum devices[END_REF]. In addition, quantum error mitigation (QEM) was introduced for error suppression on NISQ devices [START_REF] Endo | Practical quantum error mitigation for near-future applications[END_REF]. There are different QEM techniques, such as readout error mitigation [START_REF] Bravyi | Mitigating measurement errors in multiqubit experiments[END_REF], dynamical decoupling (DD) [START_REF] Souza | Robust dynamical decoupling[END_REF], crosstalk mitigation [START_REF] Murali | Software mitigation of crosstalk on noisy intermediate-scale quantum computers[END_REF][START_REF] Niu | Analyzing crosstalk error in the nisq era[END_REF], zeronoise extrapolation (ZNE) [START_REF] Li | Efficient variational quantum simulator incorporating active error minimization[END_REF], etc. Most methods require supplementary circuit executions to build the error map for mitigation. Whereas DD is one of the simplest strategies, which aims at mitigating the decoherence error (also called idle error) without any circuit overhead, and is the focus of this paper. The thrust of DD is to insert periodically a series of pulses to the idle qubits and return the qubits to their original states. There is a high probability to have idle qubits during execution due to the variation of gate latencies and limited parallelism caused by the anti-commutative gates. It has been shown in [START_REF] Das | Adapt: Mitigating idling errors in qubits via adaptive dynamical decoupling[END_REF] that the idle qubits can be almost 10 times more subject to errors if adjacent two-qubit operations are executing at the same time on IBM superconducting device. DD plays an important role in reducing the idle error and has been used in quantum volume experiments [START_REF] Jurcevic | Demonstration of quantum volume 64 on a superconducting quantum computing system[END_REF], noise spectrum characterization [START_REF] Sung | Non-gaussian noise spectroscopy with a superconducting qubit sensor[END_REF], and decoherenceprotected quantum gate implementation [START_REF] Van Der Sar | Decoherence-protected quantum gates for a hybrid solid-state spin register[END_REF], etc. Moreover, there are different DD strategies, such as Hahn echo [START_REF] Solomon | Multiple echoes in solids[END_REF], CPMG [START_REF] Meiboom | Modified spin-echo method for measuring nuclear relaxation times[END_REF], XY4 [START_REF] Viola | Dynamical decoupling of open quantum systems[END_REF], robust KDD [START_REF] Souza | Robust dynamical decoupling for quantum computing and quantum memory[END_REF], etc. They have diverse impacts on decoherence error suppression for different quantum devices. It has been shown in [START_REF] Pokharel | Demonstration of fidelity improvement using dynamical decoupling with superconducting qubits[END_REF] that DD is able to extend the lifetime of one-qubit states as well as entangled two-qubit states for IBM and Rigetti devices using XY4 sequence. But this sequence is shown to be vulnerable to experimental imperfections, while the use of robust DD was demonstrated to be capable of correcting the pulse errors on Rigetti devices [START_REF] Souza | Process tomography of robust dynamical decoupling with superconducting qubits[END_REF].

Recently, IBM released Qiskit Pulse [START_REF] Mckay | Qiskit backend specifications for openqasm and openpulse experiments[END_REF][START_REF] Alexander | Qiskit pulse: programming quantum computers through the cloud with pulses[END_REF] allowing users to design and customize the gate pulse implementations. Some works have already attempted to optimize the pulse controls and reduce the pulse durations with the help of Qiskit Pulse [START_REF] Shi | Optimized compilation of aggregated instructions for realistic quantum computers[END_REF][START_REF] Khaneja | Optimal control of coupled spin dynamics: design of nmr pulse sequences by gradient ascent algorithms[END_REF][START_REF] Egger | Adaptive hybrid optimal quantum control for imprecisely characterized systems[END_REF]. However, such method often needs additional calibrations which is time-consuming and requires a deep familiarity with quantum control. In [START_REF] Stenger | Simulating the dynamics of braiding of majorana zero modes using an ibm quantum computer[END_REF][START_REF] Earnest | Pulseefficient circuit transpilation for quantum applications on cross-resonance-based hardware[END_REF], the authors proposed a new technique to create more hardware-native pulse-efficient gates, which improves the gate fidelity without the overhead of extra calibrations.

So far, the aforementioned techniques were only tested separately for limited benchmarks and quantum hard-ware. Several questions still remain unclear: [START_REF] Preskill | Quantum computing in the nisq era and beyond[END_REF] What are the impacts of different DD sequences on specific quantum algorithms? (2) For a certain benchmark, does the impact of different DD sequences vary across different quantum chips? (3) Will the combination of DD and pulse-level optimization methods further improve the circuit fidelity? In our work, we address these questions and our main contributions can be listed as follows:

• We explore the performance of different DD sequences on various quantum applications and evaluate the experiments on several IBM devices with different qubit numbers and quantum volumes. To the best of our knowledge, this is the first attempt to illustrate the behavior of applying robust KDD sequence to IBM quantum devices.

• We combine the DD technique with pulse-efficient optimization method to demonstrate their benefits on Quantum Approximate Optimization Algorithm (QAOA) to solve Max-Cut problem.

• Based on the experimental results, we provide guidelines and insights for users to apply application-oriented dynamical decoupling and pulse-level optimization techniques.

II. BACKGROUND

A. Dynamical decoupling

Dynamical decoupling is widely used in suppressing the decoherence error by reducing the interaction between the system and the environment. Considering a systembath Hamiltonian H shown in [START_REF] Preskill | Quantum computing in the nisq era and beyond[END_REF], H s and H B being the Hamiltonian of the system and the bath respectively, and the interacting term being H SB (see (2)), where σ α i is the Pauli matrix acting on qubit i, B α i is the operator of the environment, and α ∈ {x, y, z}. DD aims at reducing the impact of system-environment interaction and various DD protocols have been developed to improve the performance of quantum computers. Here, we review the main strategies of DD implementations and a summary of these DD sequences is shown in Table I.

H = H s + H B + H SB (1)
H SB = N i=1 α∈{x,y,z} σ α i ⊗ B α i (2)
• Hahn echo. The spin-echo sequence [START_REF] Solomon | Multiple echoes in solids[END_REF] is used to reduce the inhomogeneous effects from the environmental magnetic field. It applies a π pulse to the spin system to inverse the spins after a period of time t and let the system be refocused during the same duration. At that time, T * 2 effects are removed and we can obtain a T 2 echo.

• CP and CPMG. Carr and Purcell proposed a series of π pulses separated by a constant interval, known as the CP sequence, to further reduce the effect of self-diffusion in the inhomogeneous field [START_REF] Carr | Effects of diffusion on free precession in nuclear magnetic resonance experiments[END_REF]. But, extra pulses can introduce more errors and destroy the state of the system. Therefore, Meiboom and Gill improved the CP pulse by developing the CPMG sequence [START_REF] Meiboom | Modified spin-echo method for measuring nuclear relaxation times[END_REF], retaining the CP pulse but introducing an additional phase shift in the first pulse to compensate the pulse errors.

• UDD. Hahn echo and CP/CPMG are equidistant pulses. While UDD aims at optimizing the π sequence based on CP/CPMG by varying the intervals between each pulse [START_REF] Uhrig | Keeping a quantum bit alive by optimized π-pulse sequences[END_REF]. It is proven to be the optimal pulse to suppress low frequency noise and is insensitive to thermal fluctuations. It outperforms the equidistant DD sequences especially for systems whose spectral densities have high frequencies with sharp cutoff. For other more general cases, equidistant DD sequences were shown to perform better [START_REF] Ajoy | Optimal pulse spacing for dynamical decoupling in the presence of a purely dephasing spin bath[END_REF].

• XY4. All the DD sequences above only rotate around one single axis. They are exclusively useful when the system-environment interaction is orthogonal to the rotation axis. XY4 is the simplest DD sequence to generally suppress system-environment interaction along three directions [START_REF] Viola | Dynamical decoupling of open quantum systems[END_REF]. It inserts alternatively π rotations around X and Y axes independently of the initial state.

• XY8 and XY16. DD can sometimes detriment the fidelity due to the accumulation of errors caused by pulse imperfections. One approach to reducing the errors is to combine the basic sequence with its inverse for self-correction so that the unwanted terms can be canceled [START_REF] Gullion | New, compensated carr-purcell sequences[END_REF]. XY4 is usually chosen as the basic cycle. XY8 is composed of XY4 sequence and its inverse while XY16 contains XY8 and its inverse.

• KDD. The other approach to avoid pulse imperfections is to replace each pulse of a DD sequence by a robust composite pulse, which is designed to generate ideal rotations even if there exist pulse imperfections [START_REF] Grant | Encyclopedia of nuclear magnetic resonance[END_REF]. KDD constructs a DD block using a 5-pulse composite π pulse, and combine two of such DD block with and without a phase shift π/2 as (KDD φ , KDD φ+π/2 ) 2 [START_REF] Souza | Robust dynamical decoupling for quantum computing and quantum memory[END_REF]. It is composed of 20 pulses in total.

DD has been demonstrated to have the capability to mitigate the decoherence errors on IBM and Rigetti platforms using XY4 sequences [START_REF] Pokharel | Demonstration of fidelity improvement using dynamical decoupling with superconducting qubits[END_REF]. The experiment is performed as follow: it prepares different initial states by varying the angles of the rotation gates, inserts XY4 sequences, and compares the difference between input and output states. The impacts of different DD sequences on Rigetti device are reported in [START_REF] Souza | Process tomography of robust dynamical decoupling with superconducting qubits[END_REF]. A large number of DD sequences are evaluated, including XY4, XY8, KDD, etc., and quantum process tomography is used to characterize the evolution. KDD is shown to be the most robust pulse sequence against pulse imperfections. Both papers evaluate DD sequences on simple benchmarks instead of real quantum applications, and there is no experiment to illustrate applying KDD to IBM quantum devices. Moreover, the experiments in [START_REF] Das | Adapt: Mitigating idling errors in qubits via adaptive dynamical decoupling[END_REF] show that the naive implementation of DD (inserting DD sequences to all the idle qubits when it is possible) can not always improve the circuit fidelity. Therefore, Das et al. proposed an Adaptive Dynamical Decoupling framework to estimate the DD impact for each circuit and adjust DD sequence to ensure it improves the circuit fidelity [START_REF] Das | Adapt: Mitigating idling errors in qubits via adaptive dynamical decoupling[END_REF]. This method achieves fidelity improvement but introduces a large overhead of DD impact characterization for a given application. Also, Ravi et al. proposed VAQEM [START_REF] Ravi | Vaqem: A variational approach to quantum error mitigation[END_REF], an approach that dynamically inserts DD sequences for variational algorithm with the overhead of tuning DD sequence. In our paper, instead of carefully adjusting DD sequences for better error mitigation with extra circuit overhead, we exhaustively evaluate DD sequences on extensively used quantum applications, to give a highlevel idea about if general DD techniques can really be beneficial for these applications. It is also the first attempt to implement KDD on IBM devices to check its performance. The experiments are performed on various IBM devices with different qubit numbers and quantum volumes to provide general insights about applicationoriented DD noise mitigation on IBM quantum devices.

B. Pulse-efficient technique

CN OT gate is the only two-qubit operation included in the basis gates for IBM quantum devices and its cal-ibrations are provided through the IBM quantum dashboard. It is implemented by a R ZX ( π 2 ) gate along with some single-qubit gates [START_REF] Chow | Implementing a strand of a scalable fault-tolerant quantum computing fabric[END_REF] on the device. R ZX gate is realized by the echoed cross-resonance gate [START_REF] Sheldon | Procedure for systematically tuning up crosstalk in the cross-resonance gate[END_REF], which is specific for the IBM fixed-frequency superconducting transmon qubit device due to its low overhead and high fidelity. When executing a circuit on IBM quantum hardware, every multi-qubit operation needs to be transpiled to the CN OT basis which is not flexible and less efficient.

Therefore, [START_REF] Stenger | Simulating the dynamics of braiding of majorana zero modes using an ibm quantum computer[END_REF][START_REF] Earnest | Pulseefficient circuit transpilation for quantum applications on cross-resonance-based hardware[END_REF] proposed a pulse-efficient circuit transpilation framework and has shown to achieve higher fidelity than CN OT basis transpilation for certain benchmarks. Instead of only using a R ZX (θ) with a fixed angle θ = π 2 for CN OT gate, a flexible echoed R ZX gate is implemented with arbitrary angle and R ZX (θ) = XR ZX (-θ

2 )XR ZX ( θ 2 ) to enable transpilations to R ZX basis. This method does not require any additional pulse calibration since the calibration of R ZX gate can be easily calculated from the CN OT calibrations. An example of transpiling R ZZ gate to two different basis gate sets is shown in Fig. 1. We first transpile the R ZZ gate to the IBM CN OT -basis gate sets (Fig. 1(b)) and then transpile again the original circuit to R ZX -basis gate sets (Fig. 1(c)). The duration of the second circuit is reduced by 51.1% compared to the first gate sets. This technique exposes the echo of the cross-resonance gates which enables at most one single-qubit gate between each non-echoed R ZX gate so that it can shorten the total circuit duration.

Quantum algorithms requiring a lot of two-qubit control-rotation gates, such as R ZZ or R Y Y , which can be directly compiled to R ZX gates along with some single-qubit gates, are particularly benefited from this pulse-efficient transpilation framework, for example QAOA [START_REF] Farhi | A quantum approximate optimization algorithm[END_REF], quantum hamiltonian simulation [START_REF] Papageorgiou | On the efficiency of quantum algorithms for hamiltonian simulation[END_REF], etc.

q 0 : H • H q 1 : H • H q 2 : H • H q 3 : X H (a) Bernstein-Vazirani (BV) algorithm q 0 : H X • X H • H q 1 : H X • X H • H q 2 : H X • X H • H q 3 : H • H • H (b) Hidden Shift (HS) algorithm q 0 : H • q 1 : H • • q 2 : H • • q 3 : H • • q 4 : H • (c) Graph State (GS) q 0 : • • • P ( π 2 ) H × q 1 : • • P ( π 2 ) H P ( π 4 ) • × q 2 : • P ( π 2 ) H P ( π 4 ) • P ( π 8 ) • × q 3 : H • • • × (d) Quantum Fourier Transform (QFT)
FIG. 2: Examples of different quantum circuits. Note that, the Graph State circuit is constructed linearly based on the target hardware topology.

III. METHODS

We construct DD sequences according to Table I, and n is the number of repetition time for the basic DD pulse. For Hahn echo, we insert one X or Y gate during the idle time. We set n = 2 for CP/CPMG, CP (resp.CPMG) being implemented as the sequence X -X (resp. Y -Y ). For XY4, XY8, and XY16, n is set to 1 so that the sequence of pulses is inserted once. All the aforementioned DD sequences are equidistant and symmetrical: there is a delay of τ /2 at the beginning and the end of the idle time, and a delay of τ between each DD pulse. Whereas UDD is composed of non-equidistant pulses, it acts differently from CPMG for all n > 2. As there is no clear conclusion about which repetition number n we should pick to have the best performance of UDD on IBM quantum devices, we set n = 8 as demonstrated in Qiskit tutorial. The repetition gate is set to X and Y , and is marked as UDD X and UDD Y in the results. For KDD, (θ) φ represents a rotation of θ around the axis defined by φ. Since θ φ = R Z (φ)R X (-θ)R Z (-φ), we insert 60 gates in total, where delay is only introduced between each θ φ , which means there is no space between the three gates constructing θ φ . Note that, since R Z gate is free on IBM quantum devices, KDD is translated to "only" 20 pulses in the end.

First, we evaluate the DD effects on IBM quantum computers by applying different DD sequences to various well-known quantum applications, including Bernstein-Vazirani (BV) algorithm, Hidden Shift (HS) algorithm, Quantum Fourier Transform (QFT), and Graph State (GS). The basis quantum circuit structures of these quantum applications are shown in Fig. 2. BV algorithm implements an oracle function f (x), which represents the dot product between x and a secret string s, with the objective of finding s. HS algorithm constructs an oracle that encodes two functions f and g, and there exists a secret string s such that g(x) = f (x + s). The goal of the algorithm is to find s. QFT is the quantum version of discrete Fourier transform, and is the essential part for many other quantum algorithms, such as Shor's algorithm [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF], quantum phase estimation algorithm [START_REF] Kitaev | Quantum measurements and the abelian stabilizer problem[END_REF], etc. Graph State is a quantum state prepared based on a graph. Specifically, we can build a Graph State according to a given hardware topology, where there is an edge on the graph when the two qubits are coupled, and the connection is represented by a CZ gate. It can entangle all the qubits of the device and is important for error correction.

Second, we evaluate the performance of combining different DD sequences with pulse-efficient transpilation technique. We apply them to QAOA to solve the Max-Cut problem, since QAOA ansatz is composed of R ZZ gates along with some single-qubit gates, which can be profited from the pulse-efficient method. We generate randomly 3-regular graphs using ReCirq [START_REF]Quantum AI team and collaborators[END_REF] and random graphs using Networkx with different degrees as our benchmarks. For example, we use 3-reg-4 to represent a 3-regular graph with degree of 4 (qubits) and rand-4-0.5 for a random graph with 4 nodes/qubits and a probability for edge creation of 0.5 (see Fig. 3).

We choose the following metrics for different benchmarks to demonstrate the impact of DD and pulse-level optimization technique on application fidelity.

• Probability of Successful Trial (PST) [START_REF] Tannu | Not all qubits are created equal: a case for variability-aware policies for nisqera quantum computers[END_REF]. This metric is defined by the ratio of the number of trials that give the expected result to the total number of trials, and higher is better. It is dedicated to the benchmarks with one certain correct result, such as BV algorithm and HS algorithm.

• Jensen-Shannon Divergence (JSD). It is used to measure the similarity between two probability distributions, and lower is better. It is suitable for Graph State circuit and QFT whose output is a distribution.

• Approximation ratio [START_REF] Harrigan | Quantum approximate optimization of non-planar graph problems on a planar superconducting processor[END_REF]. It is specifically designed to evaluate the performance of QAOA circuit and is defined as C /C min , where C is the expectation value obtained by the quantum computer and C min is calculated by the classical NumPyMin-imumEigensolver. We aim at maximizing the approximation ratio and 1 means a perfect solution.

IV. EXPERIMENTAL RESULTS

We perform the experiments on various IBM quantum devices with different qubit numbers and quantum volumes (QV) (see Table II). The size of the benchmarks varies depending on the quantum device. For the first experiment when evaluating the effects of applying DD sequences to different applications including BV, HS, QFT, and GS, the circuit size varies from 3 to 6 for IBM Q 7 Jakarta. Whereas for other devices, the circuit size changes from 3 to 12, since there are too many noises accumulating to obtain meaningful results for benchmarks with more than 12 qubits. When exploring the performance of combining DD and pulse-efficient optimization technique on QAOA for the second experiment, the degree of the two types of graphs (3-regular graph and random graph) ranges from 4 to 6 for IBM Q 7 Jakarta, and 4 to 12 for other devices. The QAOA ansatz has one layer with parameters initialized randomly and optimized using COBYLA optimizer on the simulator. We only execute the final ansatz with optimized parameters on the quantum hardware. All the benchmarks are compiled using Qiskit with the highest optimization level and executed 8192 times.

There are some limitations when inserting certain DD pulses to the idle time. If the DD sequences contain a large number of pulses, such as XY16 and KDD, it might not be possible to insert them to some small benchmarks whose idle time might not be long enough. Moreover, Hahn echo can only be applied if the inverse of the inserted single X or Y gate is able to be absorbed into the neighboring gates to ensure the equivalence of the quantum state. Therefore, we check if the DD pulses are actually inserted to the benchmark for each experiment, and we remove the circuit without any DD pulses inserted from the result.

In order to clearly show the impact of various DD sequences and pulse-efficient optimization method, we use the relative results for the three metrics. The original benchmark with no optimization method applied is marked as the baseline. PST is divided by the baseline and we use JSD results to divide the baseline, so that we can obtain the relative results when applying DD sequences. If the relative result is larger than one, it means that there is an improvement, and larger is better. Whereas for QAOA experiments, we use the difference between approximation ratio with DD sequence or pulseefficient technique and the baseline as the relative result due to the possible negative value of the approximation ratio. If the difference is larger than zero, it indicates an enhancement and also larger is better. Each experiment has been repeated three times and results with similar trends were obtained. We show the average of the three experiments for all the results.

We first demonstrate applying DD sequences to various quantum applications. Hahn echo is not applicable for all the benchmarks. XY16 and KDD are too long to insert for certain small BV circuits (less than 4 qubits). All the DD sequences cannot be applied to HS algorithm, since the duration of the idle time is always equal to the duration of one single-qubit gate. Thus, the idle time is too short to fit any DD sequences. The relative PST results for BV circuits, the relative JSD results for QFT and Graph State circuits are shown in Fig. 4, Fig. 5, and Fig. 6.

The quantitative analysis of the relative results is shown in Table III. For BV algorithm (see Fig. 4), if the BV circuit involves a large number of qubits, the PST fidelities can be dropped dramatically such that all the PSTs are below 0.1 even with DD applied for error mitigation. Therefore, we only show the results whose PSTs are larger than 0.1. The relative PST results demonstrate that all the DD sequences are able to enhance the BV circuit fidelity, especially UDD X. On average, the fidelity is improved by 1.09x, 3.82x, 2.79x, and 1.68x compared with the baseline for IBM Q Jakarta, Guadalupe, Toronto, and Montreal respectively. Whereas for QFT, inserting DD sequence is more favorable for circuits with more than 5 qubits. Therefore, the relative JSD results on IBM Q 7 Jakarta are not encouraging. Overall, DD can be beneficial for QFT circuits but are not as stable as for BV circuits. The fidelity is improved by 1.14x, 1.18x, and 1.28x on average for IBM Q Guadalupe, Toronto, and Montreal. For Graph State circuit, the performance of DD is also not always steady and different across IBM quantum devices. DD is helpful for Graph State circuits on IBM Q Guadalupe but not for other devices, with an increase of fidelity by 1.17x on average. The variance of the results for different DD techniques becomes smaller for relatively large-scale QFT and Graph State circuits which might be due to the accumulating errors.

To conclude, DD can always improve the fidelity for BV algorithm to different extents across IBM quantum chips. But for other applications, the performance of DD remains uncertain and can be different on various quantum devices. Moreover, for certain benchmark like HS algorithm, the idle time is always short so that DD is not applicable regardless of the circuit size.

Second, we show the results of using QAOA to solve Max-Cut problem for different graphs by employing: (1) diverse DD sequences (see Fig. 7), (2) DD sequences + pulse-efficient optimization technique (see Fig. 8). The quantitative analysis of the relative results is shown in Table IV. Most of the DD sequences can help enhance the approximate ratio for QAOA, especially CP sequence. The approximate ratio of all the graphs is improved by 6.8%, 5.9%, 3.7%, and 3.7% on average for IBM Q Jakarta, Guadalupe, Toronto, and Montreal respectively. There is no clear relationship between the level of improvement and the size of the benchmark. Comparing to the baseline circuit without applying any error mitigation technique, purely the pulse-efficient method is already able to raise the approximation value by 8.9%, 5.5%, 5.3%, and 4.8% on average for the four devices. Associating pulse-efficient technique with DD sequences can further improve the approximation ratio and the negative impact induced by DD can mostly be canceled. The combination of DD and pulse-efficient technique can improve the approximation ratio by 26.5%, 49.2%, 81.1%, 75.7% compared with only applying DD for the four IBM devices.

One interesting thing is that, even though KDD is a robust DD sequence that is designed to be robust against pulse imperfection and has shown improvements on Rigetti device, its performance is not as good as expected on IBM quantum devices. For all the quantum applications tested including QAOA circuit, there is no growth of circuit fidelity using KDD compared with other DD strategies and actually it decreases the circuit fidelity for most of the cases.

V. DISCUSSION

A. Design guideline

It is important to explore different noise mitigation and pulse-level optimization methods, including DD and pulse-efficient optimization technique to better build the quantum circuits. Here, we list several guidelines that can help the community utilize these methods to design circuits with higher fidelity.

• DD cannot always improve the circuit fidelity and it is highly application-dependent. It is recommended to use DD on specific quantum algorithms, including Bernstein-Vazirani algorithm, and QAOA.

• When applying DD sequences, it is recommended to check the transpiled circuit to verify if DD is suitable to insert.

• The robust sequence KDD does not work well on IBM quantum devices for most of the quantum algorithms tested.

• The pulse-efficient optimization technique is favorable for QAOA circuits and combined with DD, it can improve the approximation ratio.

B. Future work

As the experiments have demonstrated some discouraging effects when inserting DD sequences for certain quantum applications, exploring the hardware physics behind them becomes important. Application-dependent adaptive dynamical decoupling [START_REF] Das | Adapt: Mitigating idling errors in qubits via adaptive dynamical decoupling[END_REF] and variational algorithm-focused VAQEM [START_REF] Ravi | Vaqem: A variational approach to quantum error mitigation[END_REF] have been proposed to provide the most beneficial DD sequences but with large overhead and limited analysis of different DD strategies. A smarter approach for designing appropriate application-oriented DD sequences considering hardware physics is left to future works. Recently, DD has been proven to be able to suppress ZZ-crosstalk for fixed frequency transmon superconducting device [START_REF] Tripathi | Suppression of crosstalk in superconducting qubits using dynamical de-coupling[END_REF]. It is interesting to further investigate the performance of DD-based crosstalk suppression at application-level, so that it can contribute to the quantum parallel executions [START_REF] Niu | Enabling multi-programming mechanism for quantum computing in the nisq era[END_REF][START_REF] Niu | How parallel circuit execution can be useful for nisq computing?[END_REF]. Finally, the pulse-level optimization experiments can be delved to other quantum applications to provide more guidelines, such as VQE [START_REF] Kandala | Hardwareefficient variational quantum eigensolver for small molecules and quantum magnets[END_REF], quantum simulation [START_REF] Georgescu | Quantum simulation[END_REF], etc.

VI. CONCLUSION

Today's quantum hardware is prone to noise in the NISQ era. Therefore, circuit optimization and error mitigation approaches are required to increase the output fidelity. In this paper, we focus on two pulse-level circuit optimization methods: dynamical decoupling and pulseefficient optimization technique. First, we implement various DD strategies on IBM quantum devices including non-universal, universal, and robust ones. Second, we apply these DD sequences to several well-known quantum applications, such as QFT and Bernstein-Vazirani algorithm, to evaluate comprehensively the impact of diverse DD techniques on IBM quantum devices with dif- If the relative results ¿ 0, it means an improvement on fidelity. Otherwise, a negative impact is introduced on fidelity.

ferent characteristics. We also merge DD with pulseefficient transpilation method and investigate them on QAOA circuits to solve Max-Cut problem. Based on the experimental results, we found that DD techniques always show positive impact for some benchmarks, while for others, DD demonstrate some discouraging effects.

As there is no overhead-free application-oriented DD approach, we provide a list of design guidelines for users to better understand these pulse-level optimization methods and figure out how to improve the circuit design for various quantum applications.

  FIG. 1: (a) Original R ZZ gate with θ = π 3 . The circuit is mapped to the first two qubits of IBM Q 27 Toronto. (b) The transpilation result with basis gate sets {R Z , SX, X, CX}, and the duration is 2176 dt. dt is the sampling time for Qiskit pulses and is set to 0.2 ns. (c) The transpilation result with basis gate sets {R Z , SX, X, R ZX }, and the duration is 1025 dt. We replace R Z ( mπ 2 ) √ XR Z ( nπ 2 ) by U to simplify the circuit. m, n ∈ R and can be varied across different transpilation passes.

(a) 3 - 5 FIG. 3 :

 353 FIG.3: An example of (a) 3-regular graph with degree of 4, (b) random graph with degree of 4 and edge creation probability of 0.5.

FIG. 7 :

 7 FIG.7: Relative approximation ratio of applying DD sequences for QAOA circuit on different IBM quantum devices. Higher is better.

FIG. 8 :

 8 FIG.8: Relative approximation ratio of applying DD sequences + pulse-efficient technique for QAOA circuit on different IBM quantum devices. Higher is better.

TABLE I :

 I A summary of different DD sequences.

	DD sequences	Pulse implementation
	Hahn echo [19]	X or Y
	CP/CPMG [20, 32]	(X) n or (Y ) n
	XY4 [21]	(X -Y -X -Y ) n
	XY8 [33]	(XY 4 -XY 4) n
	XY16 [33]	(XY 8 -XY 8) n
	UDD [34]	(X) n or (Y ) n with space τ where τ = sin 2 ( πj 2n+2 ), j ∈ {1, 2, ...n}
	KDD [22]	(π) π 6 +φ -(π) φ -(π) π 2 +φ -(π) φ -(π) π 6 +φ where (θ) φ = e iθ 2 [cos(θ)σx+sin(θ)σy ] ,
		φ = 0, π 2 , 0, π 2
	n: repetition time of the basic DD cycle.
	(θ) φ : a rotation of θ around the axis defined by φ.

TABLE II :

 II The information of different IBM Q devices.

	IBM Q Jakarta Guadalupe Toronto Montreal
	n	7	16	27	27
	QV	16	16	32	128

TABLE III :

 III The relative results of applying various DD sequences to different quantum applications on four IBM Q hardware.If the relative results ¿ 1, it means that the DD sequence has a positive impact on the fidelity . Otherwise, a negative impact is introduced by DD.

						IBM Q Hardware
	Benchmarks		Jakarta		Guadalupe		Toronto		Montreal
		Max	Min	Avg Max	Min	Avg Max	Min	Avg Max	Min	Avg
	BV	1.1 (UDD X) 1.05 (KDD)	1.09 4.53 (UDD X) 3.16 (CPMG) 3.82 3.18 (UDD X) 2.44(XY16)	2.79 1.77(UDD X) 1.55 (KDD)	1.68
	QFT	1.1 (XY16) 0.89 (UDD Y) 1.01 1.17 (CPMG) 1.06 (UDD X) 1.14 1.23 (KDD)	1.14 (UDD X) 1.18 1.33 (XY4)	1.22 (UDD X) 1.28
	GS	1 (CP)	0.9 (UDD Y) 0.95 1.21 (XY4)	1.06 (UDD Y) 1.17 1.06 (CPMG) 1 (XY8)	1.03 1.02 (CP)	0.96 (XY16) 0.99
	HS					DD is not applicable

TABLE IV :

 IV The relative results of applying different methods, including only DD, only pulse-efficient method (PE), and DD+PE to QAOA circuits on four IBM Q hardware.

				IBM Q Hardware
	Methods	Jakarta		Guadalupe		Toronto	Montreal
	Max (%)	Min (%)	Avg (%) Max (%) Min (%)	Avg (%) Max (%) Min (%)	Avg (%) Max (%) Min (%)	Avg (%)
	Only DD 8.6 (UDD X) 2.4 (KDD) 6.8	7.4 (CP) 2.5 (KDD) 5.9	4.4 (CP) 2.3 (KDD) 3.7	4.7 (CP) 1.6 (KDD) 3.7
	Only PE	8.9		5.5		5.3	4.8
	DD+PE 10.4 (UDD X) 6 (KDD) 8.6	9.7 (CP) 6.8 (KDD) 8.8	7.2 (XY8) 5.8 (KDD) 6.7	7.4 (CP) 4.5 (KDD) 6.5

ACKNOWLEDGMENT

This work is funded by the QuantUM Initiative of the Region Occitanie, University of Montpellier and IBM Montpellier. The authors are very grateful to Adrien Suau for the helpful suggestions and feedback on an early version of this manuscript.

SUPPLEMENTARY INFORMATION

All the scripts to reproduce the experimental results are publicly available in https://github.com/ peachnuts/DD_PE.


Hoang La

Mickael Montassier
email: mickael.montassier@lirmm.fr

2-distance 4-coloring of planar subcubic graphs with girth at least 21

A 2-distance k-coloring of a graph is a proper vertex k-coloring where vertices at distance at most 2 cannot share the same color. We prove the existence of a 2-distance 4-coloring for planar subcubic graphs with girth at least 21. We also show a construction of a planar subcubic graph of girth 11 that is not 2-distance 4-colorable.

Introduction

A k-coloring of the vertices of a graph G = (V, E) is a map φ : V → {1, 2, . . . , k}. A k-coloring φ is a proper coloring, if and only if, for all edge xy ∈ E, φ(x) = φ(y). In other words, no two adjacent vertices share the same color. The chromatic number of G, denoted by χ(G), is the smallest integer k such that G has a proper k-coloring. A generalization of k-coloring is k-list-coloring. A graph G is L-list colorable if for a given list assignment L = {L(v) : v ∈ V (G)} there is a proper coloring φ of G such that for all v ∈ V (G), φ(v) ∈ L(v). If G is L-list colorable for every list assignment L with |L(v)| ≥ k for all v ∈ V (G), then G is said to be k-choosable or k-list-colorable. The list chromatic number of a graph G is the smallest integer k such that G is k-choosable. List coloring can be very different from usual coloring as there exist graphs with a small chromatic number and an arbitrarily large list chromatic number.

In 1969, Kramer and Kramer introduced the notion of 2-distance coloring [START_REF] Kramer | Ein Färbungsproblem der Knotenpunkte eines Graphen bezüglich der Distanz p[END_REF][START_REF] Kramer | Un problème de coloration des sommets d'un graphe[END_REF]. This notion generalizes the "proper" constraint (that does not allow two adjacent vertices to have the same color) in the following way: a 2-distance k-coloring is such that no pair of vertices at distance at most 2 have the same color (similarly to proper k-list-coloring, one can also define 2-distance k-list-coloring). The 2-distance chromatic number of G, denoted by χ 2 (G), is the smallest integer k so that G has a 2-distance k-coloring.

For all v ∈ V , we denote d G (v) the degree of v in G and by ∆(G) = max v∈V d G (v) the maximum degree of a graph G. For brevity, when it is clear from the context, we will use ∆ (resp. d(v)) instead of ∆(G) (resp. d G (v)). One can observe that, for any graph G, ∆ + 1 ≤ χ 2 (G) ≤ ∆ 2 + 1. The lower bound is trivial since, in a 2-distance coloring, every neighbor of a vertex v with degree ∆, and v itself must have a different color. As for the upper bound, a greedy algorithm shows that χ 2 (G) ≤ ∆ 2 + 1. Moreover, this bound is tight for some graphs, for example, Moore graphs of type (∆, 2), which are graphs where all vertices have degree ∆, are at distance at most two from each other, and the total number of vertices is ∆ 2 + 1. See Figure 1. By nature, 2-distance colorings and the 2-distance chromatic number of a graph depend a lot on the number of vertices in the neighborhood of every vertex. More precisely, the "sparser" a graph is, the lower its 2-distance chromatic number will be. One way to quantify the sparsity of a graph is through its maximum average degree. The average degree ad of a graph G = (V, E) is defined by ad(G) = 2|E| |V | . The maximum average degree mad(G) is the maximum, over all subgraphs H of G, of ad(H). Another way to measure the sparsity is through the girth, i.e. the length of a shortest cycle. We denote g(G) the girth of G. Intuitively, the higher the girth of a graph is, the sparser it gets. These two measures can actually be linked directly in the case of planar graphs.

A graph is planar if one can draw its vertices with points on the plane, and edges with curves intersecting only at its endpoints. When G is a planar graph, Wegner conjectured in 1977 that χ 2 (G) becomes linear in ∆(G):

Conjecture 1 (Wegner [START_REF] Wegner | Graphs with given diameter and a coloring problem[END_REF]). Let G be a planar graph with maximum degree ∆. Then,

χ 2 (G) ≤    7, if ∆ ≤ 3, ∆ + 5, if 4 ≤ ∆ ≤ 7, 3∆ 2 + 1, if ∆ ≥ 8.
The upper bound for the case where ∆ ≥ 8 is tight (see Figure 2(i)). Recently, the case ∆ ≤ 3 was proved by Thomassen [START_REF] Thomassen | The square of a planar cubic graph is 7-colorable[END_REF], and by Hartke et al. [START_REF] Hartke | The chromatic number of the square of subcubic planar graphs[END_REF] independently. For ∆ ≥ 8, Havet et al. [START_REF] Havet | List colouring squares of planar graphs[END_REF] proved that the bound is

3 2 ∆(1 + o(1)
), where o( 1) is as ∆ → ∞ (this bound holds for 2-distance list-colorings). Conjecture 1 is known to be true for some subfamilies of planar graphs, for example K 4 -minor free graphs [START_REF] Lih | Coloring the square of a K 4 -minor free graph[END_REF]. Wegner's conjecture motivated extensive researches on 2-distance chromatic number of sparse graphs, either of planar graphs with high girth or of graphs with upper bounded maximum average degree which are directly linked due to Proposition 2.

Proposition 2 (Folklore). For every planar graph G, (mad

(G) -2)(g(G) -2) < 4.
As a consequence, any theorem with an upper bound on mad(G) can be translated to a theorem with a lower bound on g(G) under the condition that G is planar.

Many results have taken the following form:

every graph G of girth g(G) ≤ g 0 and ∆(G) ≥ ∆ 0 satisfies χ 2 (G) ≤ ∆(G) + c(g 0 , ∆ 0 )
where c(g 0 , ∆ 0 ) is a small constant depending only on g 0 and ∆ 0 . Due to Proposition 2, these type of results sometimes come as a corollary of the same result on graphs with bounded maximum average degree. Table 1 shows all known such results, up to our knowledge, on the 2-distance chromatic number of planar graphs with fixed girth, either proven directly for planar graphs with high girth or came as a corollary of a result on graphs with bounded maximum average degree.

g 0 χ 2 (G) ∆ + 1 ∆ + 2 ∆ + 3 ∆ + 4 ∆ + 5 ∆ + 6 ∆ + 7 ∆ + 8 3 ∆ = 3 [27, 19] 4 5 ∆ ≥ 10 7 [1] 2 ∆ ≥ 339 [16] ∆ ≥ 312 [15] ∆ ≥ 15 [10] 1 ∆ ≥ 12 [9] 2 ∆ = 7, 8 [15] all ∆ [14] 6 ∆ ≥ 17 [3] 4 ∆ ≥ 9 [9] 2 all ∆ [11] 7 ∆ ≥ 16 [21] 2 ∆ = 4 [12] 3 8 ∆ ≥ 9 [25] 1 ∆ = 5 [8] 3 9 ∆ ≥ 7 [24] 4 ∆ = 5 [8] 3 ∆ = 3 [13] 2 10 ∆ ≥ 6 [21] 2 11 ∆ = 4 [12] 3 12 ∆ = 5 [21] 2 ∆ = 3 [7] 2 13 14 ∆ ≥ 4 [2] 4 . . . 21 ∆ = 3 5 22 ∆ = 3 [6]
Table 1: The latest results with a coefficient 1 before ∆ in the upper bound of χ 2 .

For example, the result from line "7" and column "∆ + 1" from Table 1 reads as follows : "every planar graph G of girth at least 7 and of ∆ at least 16 satisfies χ 2 (G) ≤ ∆ + 1". The crossed out cases in the first column correspond to the fact that, for g 0 ≤ 6, there are planar graphs G with χ 2 (G) = ∆ + 2 for arbitrarily large ∆ [START_REF] Borodin | Sufficient conditions for the 2-distance (∆ + 1)-colorability of plane graphs[END_REF][START_REF] Dvořák | Coloring squares of planar graphs with girth six[END_REF]. The lack of results for g = 4 is due to the fact that the graph in Figure 2(ii) has girth 4, and

χ 2 = 3∆ 2 -1 for all ∆.
We are interested in the case χ 2 (G) = ∆ + 1 as ∆ + 1 is a trivial lower bound for χ 2 (G). In particular, we are interested in planar subcubic graphs, which are graphs with maximum degree ∆ = 3. More precisely, we are trying to answer the following question:

Question 3. What is the smallest g 0 such that every planar subcubic graph G with girth g(G) ≥ g 0 verifies χ 2 (G) ≤ 4?

This question was first looked at in [START_REF] Borodin | Sufficient conditions for the 2-distance (∆ + 1)-colorability of plane graphs[END_REF] by Borodin et al. where the authors proved that g 0 ≤ 24. Later on, Borodin and Ivanova improved the upper bound on g 0 to 23 in [START_REF] Borodin | 2-distance 4-coloring of planar subcubic graphs[END_REF], then 22 in [START_REF] Borodin | 2-distance 4-colorability of planar subcubic graphs with girth at least 22[END_REF]. In this article, we aim to prove that g 0 is at most 21. In Section 2, we present the proof of Theorem 4 using the well-known discharging method. The reducible configurations are obtained by further exploiting the techniques presented in [START_REF] Borodin | 2-distance 4-colorability of planar subcubic graphs with girth at least 22[END_REF].

There was also another approach to Question 3, that is to find lower bounds on g 0 . While construction of planar graphs with χ 2 (G) ≥ ∆ + 2 for any ∆ is known for small girth [START_REF] Borodin | Sufficient conditions for the 2-distance (∆ + 1)-colorability of plane graphs[END_REF][START_REF] Dvořák | Coloring squares of planar graphs with girth six[END_REF]. The first construction with high girth (g 0 ≥ 9) was presented by Dvoȓak et al. in [START_REF] Dvořák | List-coloring squares of sparse subcubic graphs[END_REF] where the authors relied on an interesting property of 2-distance 4-colorings of vertices at distance 5 from each other. In Section 3, we improve further upon this idea to build a planar subcubic graph of girth 11 with χ 2 (G) ≥ 5. In other words, we improved the lower bound on g 0 from 9 to 11.

Proof of Theorem 4

Notations and drawing conventions.

For v ∈ V (G), the 2-distance neighborhood of v, denoted N * G (v)
, is the set of 2-distance neighbors of v, which are vertices at distance at most two from v, not including v. We also denote

d * G (v) = |N * G (v)|.
We call F (G) the set of faces of G and for all f ∈ F (G), d G (f ) is the size of face f (bridges are counted twice). We will drop the subscript and the argument when it is clear from the context. Also for conciseness, from now on, when we say "to color" a vertex, it means to color such vertex differently from all of its colored neighbors at distance at most two. Similarly, any considered coloring will be a 2-distance coloring. We will also say that a vertex u "sees" another vertex v if u and v are at distance at most 2 from each other.

Some more notations:

• A d-vertex is a vertex of degree d.

• A k-path (k + -path, k --path) is a path of length k + 1 (at least k + 1, at most k + 1) where the k internal vertices are 2-vertices and the endvertices are 3-vertices.

• We denote (k, l, m) a 3-vertex incident to a k-path, an l-path, and an m-path.

• A pair of vertices (k + , l + , m) and (m, n + , p + ) joined by an m-path will be denoted by (klm -mnp).

Similarly, a triple of vertices u = (k + , l + , m), v = (m, n + , p), and w = (p, q + , r + ) where u and v are joined by an m-path and v and w are joined by a p-path, will be denoted by (klm -mnp -pqr). This notation is taken from [START_REF] Borodin | 2-distance 4-colorability of planar subcubic graphs with girth at least 22[END_REF].

As a drawing convention for the rest of the figures, black vertices will have a fixed degree, which is represented, and white vertices may have a higher degree than what is drawn.

Let G be a counterexample to Theorem 4 with the fewest number of vertices and edges. Recall that every cycle except C 5 is colorable with 4 colors hence, since G has girth at least 21, it has maximum degree ∆ = 3. The purpose of the proof is to prove that G cannot exist. In the following sections, we will study the structural properties of G (Section 2.2). We will then apply a discharging procedure (Section 2.3).

Due to the Euler formula

(|V | -|E| + |F | = 2), we must have u∈V (G) 19 2 d(u) -21 + f ∈F (G) (d(f ) -21) = -42 < 0 (1)
We assign to each vertex u the charge µ(u) = 19 2 d(u) -21 and to each face f the charge µ(f ) = d(f ) -21. To prove the non-existence of G, we will redistribute the charges preserving their sum and obtaining a non-negative total charge, which will contradict Equation (1).

Useful observations

Before studying the structural properties of G, we will introduce some useful observations and lemmas that will be the core of the reducibility proofs of our configurations.

For a vertex u, let L(u) denote the set of available colors for u from the set {a, b, c, d}. For convenience, the lower bound on |L(u)| will be depicted on the figures below the corresponding vertex u. Lemma 5. The graphs depicted in Figure 3 are colorable unless their lists of colors are exactly what is indicated.

u 1 ≥ 1 u 2 ≥ 2 u 3 ≥ 2 u 1 ≥ 2 u 2 ≥ 1 u 3 ≥ 2 (i) Initial configuration. u 1 ⊆ {a, b} u 2 = {a, b} u 3 = {a, b} u 1 = {a, b} u 2 ⊆ {a, b} u 3 = {a, b} (ii) Forced list of colors.
Proof. If |L(u 1 ) ∪ L(u 2 ) ∪ L(u 3 )| ≥ 3, then u 1 , u 2 ,
and u 3 are easily colorable (by Hall's theorem by example). Thus, we can assume w.l.o.g. that L(u i ) ⊆ {a, b} for all 1 ≤ i ≤ 3.

Lemma 6.

Let H be a graph on n ≥ 4 vertices u 1 , u 2 , . . . , u n . Let the degree and adjacency of u 1 , u 2 , and u 3 be as depicted in Figure 4

. Let |L(u 1 )| ≥ 2, |L(u 2 )| ≥ 3, and |L(u 3 )| ≥ d * H (u 3 ) -1.
If, for every x in L(u 4 ), we have that u 4 , u 5 , . . . , u n are colorable with the respective lists

L(u 4 ) \ {x}, L(u 5 ), L(u 6 ), . . . , L(u n ), then H is colorable. u 1 ≥ 2 u 2 ≥ 3 u 3 ≥ d * -1 u 4 Figure 4: Graph H from Lemma 6.
Proof. Suppose by contradiction that H is not colorable. We remove the extra colors from L(u 1 ) and L(u 2 ) so that |L(u 1 )| = 2 and |L(u 2 )| = 3. We choose x ∈ L(u 2 ) \ L(u 1 ). By hypothesis, there exists a coloring of u 4 , u 5 , . . . , u n where u 4 is not colored x. The remaining vertices, namely u 1 , u 2 , and u 3 must not be colorable.

Since |L(u 1 )| ≥ 2, |L(u 2 )| ≥ 3, and |L(u 3 )| ≥ d * H (u 3
) -1, after coloring u 4 , . . . , u n , the lists of available colors for u 1 , u 2 , and u 3 verify |L(u 1 )| ≥ 2, |L(u 2 )| ≥ 2, and |L(u 3 )| ≥ 1. Since they are not colorable, by Lemma 5, L(u 1 ) = L(u 2 ). However, this is impossible since x ∈ L(u 2 ) \ L(u 1 ) initially and x remains in L(u 2 ) since u 4 was not colored x. Observation 7. Lemma 6 means that, by restricting the list L(u 4 ) to L(u 4 ) \ {x} for a well chosen color x ∈ L(u 4 ), we can always color u 1 , u 2 , and

u 3 last. As a result, if H -{u 1 , u 2 , u 3 } is colorable with L (u 4 ) where |L (u 4 )| = |L(u 4 )| -1 and L (u 4 ) ⊂ L(u 4 ) (L (u i ) = L(u i ) for all 5 ≤ i ≤ n),
then H is colorable. From now on, for convenience, we will say that we restrict u 4 by one color to color u 1 , u 2 , and u 3 afterwards. Proof. In the following proofs, whenever the size of a list |L(u)| ≥ i, we assume that |L(u)| = i by removing the extra colors from the list while preserving the inclusions.

(i) If L(u 1 ) = L(u 2 ), then we color u 3 with a color in L(u 3 ) \ L(u 2 ), followed by u 4 , u 2 , and u 1 in this order.

If L(u 1 ) = L(u 2 ), then we color u 2 with a color in L(u 2 ) \ L(u 1 ), followed by u 4 , u 3 , and u 1 in this order.

(ii) Since |L(u 1 )| ≥ 2, |L(u 3 )| ≥ 3, and both L(u 1 ) and L(u 3 ) are contained in {a, b, c, d}, we have a color x ∈ L(u 1 ) ∩ L(u 3 ) by the pigeonhole principle. We color u 1 and u 3 with x, then u 2 , u 2 , u 3 , and u 4 are colorable by Figure 5i.

(iii) We restrict u 2 by one color. Then, we color u 2 and u 1 in this order first. By Lemma 6, we color u 3 , u 4 , and u 5 last.

(iv) If L(u 1 ) and L(u 3 ) share a common color x, then we color u 1 and u 3 with x. The remaining vertices u 5 , u 4 , u 3 , and u 2 are colorable by Figure 5i. So, L(u 1 ) ∩ L(u 3 ) = ∅ and by symmetry, we also have

L(u 5 ) ∩ L(u 3 ) = ∅. W.l.o.g. we set L(u 3 ) = {a, b}. As a result, L(u 1 ) = L(u 5 ) = {c, d}. Recall that L(u 1 ) ⊆ L(u 2 ) and L(u 5 ) ⊆ L(u 4
). So, we can color u 1 and u 4 with c, u 2 and u 5 with d, u 3 with a, and u 3 with b.

(v) We have L(u 3 ) ⊆ L(u 3 ). Otherwise, we can color u 3 with a color in L(u 3 ) \ L(u 3 ), then u 1 , u 2 , u 3 , u 4 , and u 5 are colorable by Figure 5iii.

If L(u 1 ) and L(u 3 ) share a common color x, then we color u 1 and u 3 with x, and u 2 , u 3 , u 4 , and u 5 are colorable by Figure 5i. We also have L(u 1 ) = L(u 2 ). Otherwise, we color u 2 with a color in L(u 2 ) \ L(u 1 ), then u 5 , u 4 , u 3 , u 3 are colorable by Figure 5i, and we finish by coloring u 1 .

If L(u 1 ) ∩ L(u 3 ) = ∅,
Since x ∈ L(u 3 ) ∩ L(u 5 ) ∩ L(u 2 ) ∩ L(u 1 ), we color u 1 , u 3 , and u 5 with x, then we color u 2 , u 4 , and u 3 in this order.

(vii) If there exists x ∈ L(u 3 ) \ L(u 5 ), then we color u 3 with x, then u 3 , u 1 , u 2 , u 4 , u 4 , and u 5 in this order.

If L(u 3 ) = L(u 5 ), then we color u 4 with a color y in L(u 4 ) \ L(u 5 ). Recall that L(u 3 ) ⊆ L(u 3 ), so y / ∈ L(u 3 ) ∪ L(u 3 ) ∪ L(u 5 ). We color u 1 , u 2 , u 3 , and u 3 by Figure 5i. Finally, we finish by color u 4 and u 5 in this order.

(viii) If there exists two same sets of colors between L(u 2 ), L(u 4 ), and L(u 3 ), say L(u 2 ) = L(u 4 ), then we color u 3 with x ∈ L(u 3 )\L(u 2 ). Recall that L(u 1 ) ⊆ L(u 2 ) and L(u 5 ) ⊆ L(u 4 ) so x / ∈ L(u 1 )∪L(u 2 )∪L(u 4 )∪L(u 5 ). We finish by coloring u 3 , u 3 , u 1 , u 2 , u 4 , u 5 in this order.

If L(u 2 ), L(u 4 ), and L(u 3 ) are all different, then we color the graph as follows. By the pigeonhole principle, two sets between L(u 1 ), L(u 5 ), and L(u 3 ) must share a common color, say L(u 1 ) ∩ L(u 5 ) = ∅. In other words, |L(u 1 ) ∪ L(u 5 )| ≤ 3. Then, we color u 3 with a color in L(u 3 ) \ (L(u 1 ) ∪ L(u 5 )). We color u 3 and u 3 in this order. Now, we can color u 2 and u 4 since they see the same two colors but initially L(u 2 ) = L(u 4 ). Finally, we finish by coloring u 1 and u 5 . (ix) If L(u 1 ) = L(u 2 ), then we restrict L(u 3 ) to L(u 3 ) \ L(u 2 ). We color u 3 , u 4 , u 5 , u 6 by Figure 5i, then we finish by coloring u 2 and u 1 in this order.

u 1 ≥ 2 u 2 ≥ 2 u 3 ≥ 3 u 4 ≥ 2 (i) u 1 ≥ 2 u 2 ≥ 3 u 3 ≥ 4 u 4 ≥ 3 u 2 ≥ 3 u 3 ≥ 3 (ii) u 1 ≥ 2 u 2 ≥ 2 u 3 ≥ 3 u 4 ≥ 3 u 5 ≥ 2 (iii) u 1 ≥ 2 u 2 ≥ 3 u 3 ≥ 4 u 4 ≥ 3 u 5 ≥ 2 u 3 ≥ 2 (iv) L(u1) ⊆ L(u2) and L(u5) ⊆ L(u4). u 1 ≥ 2 u 2 ≥ 3 u 3 ≥ 3 u 4 ≥ 4 u 5 ≥ 2 u 3 ≥ 2 (v) u 1 ≥ 2 u 2 ≥ 2 u 3 ≥ 4 u 4 ≥ 3 u 5 ≥ 2 u 3 ≥ 3 (vi) u 1 ≥ 2 u 2 ≥ 4 u 3 ≥ 3 u 4 ≥ 4 u 5 ≥ 3 u 3 ≥ 2 u 4 ≥ 3 (vii) L(u 3 ) ⊆ L(u3). u 1 ≥ 2 u 2 ≥ 3 u 3 ≥ 4 u 4 ≥ 3 u 5 ≥ 2 u 3 ≥ 3 u 3 ≥ 2 (viii) L(u1) ⊆ L(u2), L(u 3 ) ⊆ L(u 3 ), and L(u5) ⊆ L(u4). u 1 ≥ 2 u 2 ≥ 2 u 3 ≥ 4 u 4 ≥ 3 u 5 ≥ 2 u 6 ≥ 2 (ix) u 1 ≥ 2 u 2 ≥ 3 u 3 ≥ 4 u 4 ≥ 4 u 5 ≥ 2 u 6 ≥ 2 u 3 ≥ 3 u 3 ≥ 2 (x) L(u1) ⊆ L(u2) and L(u 3 ) ⊆ L(u 3 ). u 1 ≥ 2 u 2 ≥ 3 u 3 ≥ 3 u 4 ≥ 4 u 5 ≥ 4 u 6 ≥ 2 u 7 ≥ 2 u 3 ≥ 2 (xi) u 1 ≥ 2 u 2 ≥ 2 u 3 ≥ 4 u 4 ≥ 4 u 5 ≥ 3 u 6 ≥ 4 u 7 ≥ 3 u 5 ≥ 2 u 6 ≥ 3 (xii) L(u 5 ) ⊆ L(u5).
If there exists x ∈ L(u 1 ) \ L(u 2 ), then we color u 1 with x. Finally, u 6 , u 5 , u 4 , u 3 , and u 2 are colorable by Figure 5iii.

(x) If L(u 5 ) = L(u 6 ), then we restrict L(u 4 ) to L(u 4 ) \ L(u 5 ). Recall that we have L(u 1 ) ⊆ L(u 2 ) and L(u 3 ) ⊆ L(u 3 ). We can thus color u 1 , u 2 , u 3 , u 4 , u 3 , and u 3 by Figure 5iv. We finish by coloring u 5 and u 6 in this order.

If there exists a ∈ L(u 6 ) \ L(u 5 ), then we color u 6 with a. Observe that L(u 5 ) ⊆ {b, c, d} = L(u 4 ) after we color u 6 with a. Recall that we also have L(u 1 ) ⊆ L(u 2 ) and L(u 3 ) ⊆ L(u 3 ). So, we color the remaining vertices u 1 , u 2 , u 3 , u 3 , u 3 , u 4 , and u 5 by Figure 5viii (xi) If L(u 6 ) = L(u 7 ), then we restrict L(u 5 ) to L(u 5 )\L(u 6 ). We color u 1 , u 2 , u 3 , u 3 , u 4 , and u 5 by Figure 5v. We finish by coloring u 6 and u 7 in this order.

If there exists x ∈ L(u 7 ) \ L(u 6 ), then we color u 7 with x. We restrict u 3 by one color to color u 4 , u 5 , and u 6 last by Lemma 6. Then, u 3 , u 3 , u 2 , and u 1 are colorable by Figure 5i.

(xii) If L(u 1 ) = L(u 2 ), then we restrict L(u 3 ) to L(u 3 ) \ L(u 2 ). We color u 3 , u 4 , u 5 , u 5 , u 6 , u 6 , and u 7 by Figure 5vii. Then, we finish by coloring u 2 and u 1 in this order.

If there exists x ∈ L(u 2 ) \ L(u 1 ), then we color u 2 with x. We color u 5 , u 5 , u 4 , u 6 , u 6 , and u 7 by Figure 5ii. Finally, we finish by coloring u 3 and u 1 in this order.

Structural properties of

G Lemma 9. Graph G is connected.
Otherwise a component of G would be a smaller counterexample.

Lemma 10. The minimum degree of G is at least 2.

By Lemma 9, the minimum degree is at least 1 or G would be a single isolated vertex which is 4-colorable. If G contains a degree 1 vertex v, then we can simply remove the unique edge incident to v and 2-distance color the resulting graph, which is possible by minimality of G. Then, we add the edge back and color v (at most 3 constraints and 4 colors).

Lemma 11 ([6] Lemmas 10,11, and 12). Graph G has no:

(i) 6 + -paths (ii) (1 + , 4 + , 5 + ) (iii) (2 + , 3 + , 4 + ) (iv) (3 + , 3 + , 3 + ) (v) (330 -045) (vi) (431 -133)
The proofs of the reducibility of these configurations are presented in [START_REF] Borodin | 2-distance 4-colorability of planar subcubic graphs with girth at least 22[END_REF] with the same notations. These configurations were reduced for planar subcubic graphs of girth at least 22 where all 3-vertices and 2-vertices on the incident paths are distinct, but the same proofs hold for G since the girth is still high enough for all vertices to remain distinct.

The following configurations are new or stronger versions of configurations in [START_REF] Borodin | 2-distance 4-colorability of planar subcubic graphs with girth at least 22[END_REF].

Lemma 12. Graph G cannot contain the following pairs: Proof. First, we define the following notations:

(i) (430 -024) (ii) (540 -014) (iii) (431 -114) (iv) (422 -223) (v) (422 -214) (vi) (412 -233) (vii) (332 -233) u k+1 u k u 1 u v m v 1 v v m+1 v m+p v m+p+1 u 1 u l u l+1 v 1 v n v n+1
• Let u = (k + , l + , m) and v = (m, n + , p + ) form the pair (klm -mnp).

• Let uu 1 u 2 . . . u k+1 be the k + -path incident to u.

• Let uu 1 u 2 . . . u l+1 be the l + -path incident to u.

• Let vv 1 v 2 . . . v m u be the m-path incident to u and v.

• Let vv 1 v 2 . . . v n+1 be the n + -path incident to v.

• Let vv m+1 v m+2 . . . v m+p+1 be the p + -path incident to v.

• For every pair (klm -mnp) from (i) to (vii), we define the subgraph

H = {u, v, u 1 , u 2 , . . . , u k-1 , u 1 , u 2 , . . . , u l-1 , v 1 , v 2 , . . . , v m+p-1 , v 1 , v 2 , . . . , v n-1 }.
First, observe that all vertices in H are distinct since G has girth at least 21. In the following proofs, we will always color G -H first, which is possible by minimality of G. For each vertex of H, its list of available colors will always be {a, b, c, d} from which we removed the colors it sees on its neighbors from G -H. Then, we will show that the coloring of G -H is extendable to H using colorable graphs from Lemma 8. For convenience, we will cite Figure 5 from now on.

Also observe that when two adjacent vertices x 1 , x 2 in H sees a common color with |L(x 1 )| ≤ |L(x 2 )|, then L(x 1 ) ⊆ L(x 2 ). This simple remark will be used throughout the proofs, mostly to justify the use of Figure 5(iv), (vii), (viii), (x), and (xii). For conciseness, we will state the inclusions directly when needed.

(i) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict v by one color to color v 1 , v 2 , and v 3 afterwards. Finally, v 1 , v, u, u 1 , and u 2 are colorable by Figure 5iii.

(ii) We restrict v by one color to color v 1 , v 2 , and v 3 last. We restrict u 1 by one color to color u 2 , u 3 , and u 4 afterwards. Finally, we color v, then u 1 , u, u 1 , u 2 , and u 3 are colorable by Figure 5iii.

(iii) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict v by one color to color v 2 , v 3 , and v 4 afterwards. Finally, we color v, then v 1 , u, u 1 , and u 2 are colorable by Figure 5i.

(iv) We restrict u by one color to color u 1 , u 2 , and u 3 last. Then, v 4 , v 3 , v, v 1 , v 1 , v 2 , u, and u 1 are colorable by Figure 5xi.

(v) We restrict v by one color to color v 3 , v 4 , and v 5 last. We restrict u by one color to color u 1 , u 2 , and u 3 afterwards. Finally, we color v, then u 1 , u, v 2 , and v 1 are colorable by Figure 5i.

(vi) We restrict u by one color to color u 1 , u 2 , and u 3 last. Then, we color u and observe that since

L(v 2 ) ⊆ L(v 1 ), L(v 2 ) ⊆ L(v 1 ), and L(v 4 ) ⊆ L(v 3 ), v 2 , v 1 , v, v 1 , v 2 , v 3
, and v 4 are colorable by Figure 5viii.

(vii) We color v with x ∈ L(v) \ L(v 1 ). Observe that L(v 2 ) ⊆ L(v 1 ) so x / ∈ L(v 1 ) ∪ L(v 2 )
. Then, we color v 4 , and v 3 in this order. Since L(u 2 ) ⊆ L(u 1 ), L(u 2 ) ⊆ L(u 1 ), and L(v 1 ) ⊆ L(v 2 ), u 2 , u 1 , u, u 1 , u 2 , v 2 and v 1 are colorable by Figure 5viii. Finally, we finish by coloring v 1 and v 2 .

Lemma 13. Graph G cannot contain the following triples: Proof. We will use similar notations to the proofs of Lemma 12:

(i) (550 --045) (ii) (440 --024) (iii) (550 --134) (iv) (420 --134) (v) (550 --224) (vi) (540 --214) (vii) (540 --233) (viii) (420 --214) (ix) (420 --233) (x) (431 --124) (xi) (421 --124) (xii) (431 --224) (xiii) (421 --233) (xiv) (421 --214) (xv) (422 --214) (xvi) (332 --224) (xvii) (332 --233) (xviii) (332 --214) (xix) (412 --214) u k+1 u k u 1 u v m v 1 v v m+1 v m+p w w 1 w r w r+1 u 1 u l u l+1 v 1 v n v n+1 w 1 w q w q+1
• Let u = (k + , l + , m), v = (m, n + , p), and w = (p, q + , r + ) form the triple (klm -mnp -pqr).

• Let uu 1 u 2 . . . u k+1 be the k + -path incident to u.

• Let uu 1 u 2 . . . u l+1 be the l + -path incident to u.

• Let vv v 2 . . . v m u be the m-path incident to u and v.

• Let vv v 2 . . . v n+1 be the n + -path incident to v.

• Let vv m+1 v m+2 . . . v m+p w be the p-path incident to v and w.

• Let ww 1 w 2 . . . w q+1 be the q + -path incident to w.

Case 2: Suppose that k + l + m ≤ 7 and that u is a (2 -, 5 -, 2 -). First, observe that when u is a (2 -, 2 -, 2 -), it gives at most 5 2 along every incident path except for the case of R2(i), when it shares a 2-path with a (2, 2, 5). Indeed, by R0, u gives at most 5 2 to an adjacent 3-vertex. By R1 and R3, u gives 1 to the 2-vertex on the 1-path and at most 3 2 to the other endvertex. By R2(ii), R2(iii), and R3, u gives 2 to the 2-vertices on the 2-path and at most 1 2 to the other endvertex. As a result, u, a (2 -, 2 -, 2 -) that does not share a 2-path with a (2, 2, 5), verifies

µ * (u) ≥ 15 2 -3 • 5 2 = 0
In other words, for the following values of k, l, m, we only need to look at 2 ≤ l ≤ 5. Moreover, when l = 2, we can assume w.l.o.g. that the other endvertex of the 2-path is a (2, 2, 5) since k, l, and m are interchangeable.

Let v = (i, j, k) share the k-path with u and let w = (m, n, p) share the m-path with u (see Figure 8). For each case, only R3, Rk and Rm apply, with the additional R2(i) when l = 2. • If u is a (0, 5 -, 0), then we distinguish the two following cases:

If 2 ≤ l ≤ 3, then u gives at most 3 along the l-path: either 3 to the 2-vertices in the case of a 3-path or 2 to the 2-vertices and 3 4 to the other endvertex by R2(i). Since (550 -020 -045) is reducible by Lemma 13(i), u cannot give 5 2 twice to v and w by R0. So at worst, we have

µ * (u) = 15 2 -3 - 5 2 - 3 2 = 1 2
If 4 ≤ l ≤ 5, then u gives at most 5 to the 2-vertices along the l-path. Since (440 -040 -024) is reducible by Lemma 13(ii), u cannot give 3 2 twice to v and w by R0. So at worst, we have

µ * (u) = 15 2 -5 - 3 2 - 1 2 = 1 2
• If u is a (0, 5 -, 1), then we distinguish the two following cases:

If 2 ≤ l ≤ 3, then u gives at most 3 along the l-path: either 3 to the 2-vertices in the case of a 3-path or 2 to the 2-vertices and 3 4 to the other endvertex by R2(i). Since (550 -021 -134) and (420 -031 -134) are reducible respectively by Lemma 13(iii) and (iv), u cannot give 5 2 twice to v and w by R0 and R1 (1 + 3 2 in the case of R1(i)). So at worst, we have

µ * (u) = 15 2 -3 - 5 2 - 3 2 = 1 2
If 4 ≤ l ≤ 5, then u gives at most 5 along the l-path.

-If w is a (1, 3 + , 4 + ), then v cannot be a (4 + , 2 + , 0) since (420-031-134) is reducible by Lemma 13(iv). As a result, u gives at most 3 2 along the 1-path by R1 and nothing to its adjacent 3-vertex by R0. So at worst, we have

µ * (u) = 15 2 -5 -1 - 3 2 = 0
-If w is not a (1, 3 + , 4 + ), then u gives at most 1 2 along the 1-path by R1 and at most 1 2 to its adjacent 3-vertex by R0 since (540 -014) is reducible by Lemma 12(ii). So at worst, we have

µ * (u) = 15 2 -5 -1 - 1 2 - 1 2 = 1 • If u is a (3,
µ * (v) ≥ 15 2 -4 -3 = 1 2
To conclude, we started with a charge assignment with a negative total sum, but after the discharging procedure, which preserved that sum, we end up with a non-negative one, which is a contradiction. In other words, there exists no counter-example G to Theorem 4.

A non 4-colorable subcubic planar graph of girth 11

In [START_REF] Dvořák | List-coloring squares of sparse subcubic graphs[END_REF], Dvoȓák, Skrekovski, and Tancer presented a non 4-colorable, planar, and subcubic graph with girth at least 9. The main building block of that graph relies upon an interesting property of 4-colorings on path of length 5. Using the same property we managed to build a non 4-colorable planar subcubic graph of girth 11.

Lemma 14.

Let H be a subcubic graph of girth at least 11 and φ a 4-coloring of H. Let u 1 u 2 u 3 u 4 u 5 u 6 be a path of length 5 in H, if φ(u 1 ) = φ(u 6 ), then φ(u 2 ) = φ(u 5 ). Proof. Since H has girth 11, all considered vertices are distinct. We assume w.l.o.g. that φ(u 1 ) = φ(u 6 ) = φ(v 0 ) = a. By Lemma 14, since φ(u 1 ) = φ(u 6 ), we must have φ(u 2 ) = φ(u 5 ). W.l.o.g. we set φ(u 2 ) = φ(u 5 ) = b. As a result, we have {φ(u 3 ), φ(u 4 )} = {c, d}. We assume w.l.o.g. that φ(u 3 ) = c and φ(u 4 ) = d. Now, suppose by contradiction that φ(v 1 ) = c. By Lemma 14, since φ(u 3 ) = φ(v 1 ), we must have φ(u 1 ) = φ(u 4 ) = a. However, this is impossible since u 4 sees v 0 which is colored a. By symmetry, the same argument holds when φ(v 1 ) = d. Finally, since v 1 also sees v 0 , thus φ(v 1 ) / ∈ {a, c, d}, and so φ(v 1 ) = b = φ(u 2 ) = φ(u 5 ). • G = (u, v) is planar and subcubic.

Proof. Since

• G = (u, v) has girth 11.

• The distance in G = (u, v) between u and v is 7.

• Every 4-coloring φ of G = (u, v) satisfies φ(u) = φ(v).
Proof. One can verify that G = (u, v) is planar, subcubic, has girth 11, and that the distance between u and v is 7 thanks to Figure 11i. It remains to prove that φ(u) = φ(v) for every 4-coloring φ of G = (u, v).

Suppose by contradiction that there exists a 4-coloring φ such that φ(u) = φ(v) = a. We can assume w.l.o.g. that φ(u 1 ) = b, φ(u 2 ) = c, and φ(v 5 ) = d. Since u 6 sees v which is colored a, we distinguish the following cases based on φ(u 6 ):

• If φ(u 6 ) = b, then φ(u 5 ) = φ(u 2 ) = c by Lemma 14 as φ(u 6 ) = φ(u 2 ). As a result, φ(v 1 ) = d. Since v 2 and v 4 both see b and d, we have {φ(v 2 ), φ(v 4 )} = {a, c}. Now, v 3 sees {φ(v 1 ), φ(v 2 ), φ(v 4 ), φ(v 5 )} = {d, a, c}, so φ(v 3 ) = b. Finally, v 7 sees {φ(v 2 ), φ(v 3 ), φ(v 4 )} = {a, b, d}, hence φ(v 7 ) = d. However, this is impossible since φ(u 1 ) = φ(u 6 ) = φ(v 3 ) = b, thus φ(u 2 ) = φ(u 5 ) = φ(v 7 ) = c by Lemma 15.
• If φ(u 6 ) = c, then we have the two following cases: • G = (u, v) is planar and subcubic.

-If φ(v 1 ) = b, then φ(v 2 ) = φ(v 5 ) =
• G = (u, v) has girth 11.

• The distance in G = (u, v) between u and v is 10.

• Every 4-coloring φ of G = (u, v) satisfies φ(u) = φ(v).

Figure 12

Proof. One can verify that G = (u, v) is planar, subcubic, has girth 11, and that the distance between u and v is 10 thanks to Figure 12i and Lemma 16. It remains to prove that φ(u) = φ(v) for every 4-coloring φ of G = (u, v). Suppose by contradiction that there exists a 4-coloring φ of G = (u, v) such that φ(u) = φ(v), say φ(u) = a. We only need to observe that w 3 and w 4 cannot be colored a thanks to G = (u, v) and w 1 and w 2 cannot be colored a since they see v. This is a contradiction as we have four vertices at distance two pairwise but only three colors left.

Lemma 18.

The graph G = (u, v) in Figure 13i has the following properties:

• G = (u, v) is planar and subcubic.

• G = (u, v) has girth 11.

• The distance in G = (u, v) between u and v is 3.

• Every 4-coloring φ of G = (u, v) satisfies φ(u) = φ(v). As a direct consequence of Lemma 17 and Lemma 18, we get the following lemma.

Lemma 19. The graph G in Figure 14 is a planar subcubic graph of girth 11 with χ 2 (G) ≥ 5.

In [START_REF] Dvořák | List-coloring squares of sparse subcubic graphs[END_REF], the authors also proved the NP-completeness of the problem of deciding if a planar subcubic graph of girth 9 is 4-colorable using a gadget that can reproduce colors at a far enough distance to preserve the girth condition. The same proof can be adapted directly to prove the NP-completeness of deciding if a planar subcubic graph of girth 11 is 4-colorable by using a concatenation of G = (u, v) to get a large enough distance.

  The Moore graph of type (3,2): the Petersen graph.

(

  iii) The Moore graph of type (7,2): the Hoffman-Singleton graph.

Figure 1 :

 1 Figure 1: Examples of Moore graphs for which χ 2 = ∆ 2 + 1.

Figure 2 :

 2 Figure 2: Graphs with χ 2 ≈ 3 2 ∆

Theorem 4 .

 4 If G is a planar subcubic graph with g(G) ≥ 21, then χ 2 (G) ≤ 4.

Figure 3 :

 3 Figure 3: An useful non-colorable graph on three vertices.

Lemma 8 .

 8 The graphs depicted in Figure5are all colorable.

  then w.l.o.g. we set L(u 1 ) = {a, b} and L(u 3 ) = {c, d}. Since |L(u 2 )| ≥ 3, w.l.o.g. we color u 2 with a then u 1 with b. As both L(u 3 ) and L(u 3 ) contain {c, d}, we still have |L(u 3 )| ≥ 2 and |L(u 3 )| ≥ 2, thus u 3 , u 3 , u 4 , and u 5 are colorable by Figure 5i. (vi) By the pigeonhole principle, there exists x ∈ L(u 3 ) ∩ L(u 5 ). If x / ∈ L(u 2 ), then we color u 3 and u 5 with x. The remaining vertices u 1 , u 2 , u 3 , and u 4 are colorable by Figure 5i. So x ∈ L(u 2 ).

Figure 5 :

 5 Figure 5: Colorable graphs.

Figure 6 :

 6 Figure 6: Lemma 12 notations.

Figure 7 :

 7 Figure 7: Lemma 13 notations.

  Figure 8

Lemma 15 .

 15 H has girth at least 11, all considered vertices are distinct. Suppose by contradiction that φ(u 1 ) = φ(u 6 ) but φ(u 2 ) = φ(u 5 ). W.l.o.g. we set φ(u 1 ) = φ(u 6 ) = a, φ(u 2 ) = b, and φ(u 5 ) = c. Since u 3 sees u 1 , u 2 , and u 5 , colored respectively a, b, and c, it must be colored d. Finally, u 4 sees u 2 , u 3 , u 5 , and u 6 , colored respectively by b, d, c, and a. Thus, u 4 is non-colorable, which is a contradiction since φ is a 4-coloring of H. Let H be a subcubic graph of girth 11 and φ a 4-coloring of H. Let u 1 u 2 u 3 u 4 u 5 u 6 , u 3 u 1 u 2 u 3 u 4 v 1 , u 4 u 1 u 2 u 3 u 4 v 1 be paths of length 5 in H. Let v 0 / ∈ {u 4 , u 4 } be adjacent to v 1 . If φ(u 1 ) = φ(u 6 ) = φ(v 0 ), then φ(u 2 ) = φ(u 5 ) = φ(v 1 ).

6 aFigure 9 :

 69 Figure 9: A non-valid coloring of H in Lemma 14.

Figure 10 :Lemma 16 .

 1016 Figure 10: A non-valid coloring of H in Lemma 15. Lemma 16. The graph G = (u, v) in Figure 11i has the following properties:

-

  d by Lemma 14 as φ(v 1 ) = φ(u 1 ). As a result, φ(u 5 ) = d and φ(v 6 ) = a. Since v 3 and v 4 both see b and d, we have {φ(v 3 ), φ(v 4 )} = {a, c}. Now, v 7 sees {φ(v 2 ), φ(v 3 ), φ(v 4 )} = {d, a, c}, so φ(v 7 ) = b. Since u 3 sees b, c, and d, φ(u 3 ) = a and consequently, φ(u 4 ) = b and φ(w 1 ) = c. However, this is impossible sinceφ(u 4 ) = φ(v 7 ) = φ(v 1 ) = b, thus φ(w 1 ) = φ(w 4 ) = φ(v 6 ) = a by Lemma 15. If φ(v 1 ) = d, then φ(u 5 ) = b. All three vertices v 2 , v 3 , and v 4 see d, so {φ(v 2 ), φ(v 3 ), φ(v 4 ), } = {a, b, c}. As a result, φ(v 7 ) = d. Both u 3 and u 4 see b and c, so {φ(u 3 ), φ(u 4 )} = {a, d}. Since w 1 sees {φ(u 3 ), φ(u 4 ), φ(u 5 )} = {a, d, b}, φ(w 1 ) = c. Due to Lemma 15, we must have φ(u 4 ) = a. Otherwise, by Lemma 15, φ(u 4 ) = d = φ(v 7 ) = φ(v 1 ) and φ(w 1 ) = φ(w 4 ) = φ(v 6 ) = c which is impossible since v 6 sees u 6 colored c. Thus, φ(u 3 ) = d and φ(t 1 ) = b. However, this is also impossible since φ(u 3 ) = φ(v 7 ) = φ(v 5 ) = d, thus φ(t 1 ) = φ(t 4 ) = φ(v8 ) = b by Lemma 15 and v 8 sees u 1 colored b. • If φ(u 6 ) = d, then φ(v 1 ) = φ(v 4 ) by Lemma 14 as φ(u 6 ) = φ(v 5 ). Since v 4 sees b and d and v 1 sees a and d, φ(v 4 ) = φ(v 1 ) = c. As a result, φ(u 5 ) = b and φ(v 8 ) = a. Both v 2 and v 3 see c and d, so {φ(v 2 ), φ(v 3 )} = {a, b}. Now, v 7 sees {φ(v 2 ), φ(v 3 ), φ(v 4 )} = {a, b, c}, so φ(v 7 ) = d. Since u 4 sees d, b, and c, φ(u 4 ) = a and consequently, φ(u 3 ) = d and φ(t 1 ) = b. However, this is impossible since φ(u 3 ) = φ(v 7 ) = φ(v 5 ) = d, thus φ(t 1 ) = φ(t 4 ) = φ(v 8 ) = a by Lemma 15.

  u

  drawing of G = (u, v).

Figure 11 Lemma 17 .

 1117 Figure 11

  The gadget G = (u, v) in Lemma 17.

  drawing of G = (u, v).

  The gadget G=(u, v) in Lemma 18.

  Simplified drawing of G=(u, v).

Figure 13 Proof.Figure 14 :

 1314 Figure 13

  1, 3), then u can only give charge by R1 and R3. Since (431-133) is reducible by Lemma 11(vi), u can give at most 1 2 to another 3-vertex by R1(ii). As a result, If u is a (4, 0, 3), then u can only give charge by R0 and R3. Since (430-024) is reducible by Lemma 12(i), u actually does not give charge by R0. As a result,

	µ * (v) ≥	15 2	-	1 2	-3 -3 -1 = 0
	•

• Let ww 1 w 2 . . . w r+1 be the r + -path incident to u.

• For every triple (klm -mnp -pqr) from (i) to (xix), we define the subgraph H = {u, v, w, u 1 , u 2 , . . . , u k-1 , u 1 , u 2 , . . . , u l-1 , v 1 , v 2 , . . . , v m+p , v 1 , v 2 , . . . , v n-1 , w 1 , w 2 , . . . , w q-1 , w 1 , w 2 , . . . , w r-1 }.

Similarly, all vertices in H are distinct since G has girth at least 21. We will color G -H by minimality of G first, then extend that coloring to H using Figure 5.

(i) We restrict u 1 by one color to color u 2 , u 3 , and u 4 last. We restrict u 1 by one color to color u 2 , u 3 , and u 4 afterwards. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We restrict w 1 by one color to color w 2 , w 3 , and w 4 afterwards. Now, we color v 1 , v, w, u, u 1 , and u 1 by Figure 5ii. Then, we color w 1 .

(ii) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict u again by one color to color u 1 , u 2 , and u 3 afterwards. We restrict v by one color to color v 1 , v 2 , and v 3 afterwards. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We color the remaining vertices w 1 , w, v, and u by Figure 5i.

(iii) We restrict u 1 by one color to color u 2 , u 3 , and u 4 last. We restrict u 1 by one color to color u 2 , u 3 , and u 4 afterwards. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We restrict v 1 by one color to color w, w 1 , and w 2 afterwards. The remaining vertices v 1 , v, v 1 , u, u 1 , and u 1 are colorable by Figure 5ii.

(iv) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We restrict v 1 by one color to color w, w 1 , and w 2 afterwards. The remaining vertices u 1 , u, v, v 1 , v 1 , and v 2 are colorable by Figure 5vi.

(v) We restrict u 1 by one color to color u 2 , u 3 , and u 4 last. We restrict u 1 by one color to color u 2 , u 3 , and u 4 afterwards. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. The remaining vertices (vi) We restrict u 1 by one color to color u 2 , u 3 , and u 4 last. We restrict w by one color to color w 1 , w 2 , and

. Now, we color w, v 2 , v 1 in this order. The vertices u 1 , u, u 1 , u 2 , and u 3 are colorable by Figure 5iii. Then, we color the remaining vertices v 1 and v 2 in this order.

(vii) We restrict u 1 by one color to color u 2 , u 3 , and u 4 last. We color w with x ∈ L(w) \ L(w 1 ). Observe that L(w 2 ) ⊆ L(w 1 ) so x / ∈ L(w 1 ) ∪ L(w 2 ). We color

. Now, we color w 2 , w 1 , v 2 , v 1 in this order. The vertices u 1 , u, u 1 , u 2 , and u 3 are colorable by Figure 5iii. Then, we color the remaining vertices v 1 , v 2 , w 1 , and w 2 in this order.

(viii) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We restrict v by one color to color v 1 , v 2 , and v 3 afterwards. We color w then the remaining vertices u 1 , u, v, v 1 , and v 2 are colorable by Figure 5iii.

(ix) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict v by one color to color v 1 , v 2 , and v 3 afterwards. We color w with x ∈ L(w) \ L(w 1 ). Observe that L(w 2 ) ⊆ L(w 1 ) so x / ∈ L(w 1 ) ∪ L(w 2 ). We color w 2 and w 1 in this order. The vertices u 1 , u, v, v 1 , and v 2 are colorable by Figure 5iii. Now, we color the remaining vertices w 1 and w 2 in this order.

(x) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict v 1 by one color to color u, u 1 , and u 2 afterwards. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We restrict L(v 2 ) to L(v 2 ) \ L(w 1 ). We color the vertices w, v 2 , v, v 1 , v 1 and v 2 by Figure 5vi. Then, we color the remaining vertex w 1 .

(xi) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict v by one color to color v 1 , v 2 , and v 3 afterwards. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We restrict L(v 1 ) to L(v 1 ) \ L(u 1 ). We color w 1 , w, v 2 , v, v 1 , and u by Figure 5ix. Then, we color the remaining vertex u 1 .

(xii) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict v 1 by one color to color u, u 1 , and u 2 afterwards. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We color the remaining vertices w 1 , w, v 3 , v 2 , v, and v 1 by Figure 5ix.

(xiii) We restrict u by one color to color u 1 , u 2 , and u 3 last. We color w with x ∈ L(w) \ L(w 1 ). Observe that L(w 2 ) ⊆ L(w 1 ) so x / ∈ L(w 1 ) ∪ L(w 2 ). We color w 2 and w 1 in this order. The vertices

. Now, we color the remaining vertices w 1 and w 2 in this order.

(xiv) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We color w then the remaining vertices

(xv) We restrict u by one color to color u 1 , u 2 , and u 3 last. We restrict w by one color to color w 1 , w 2 , and w 3 afterwards. We color w then the remaining vertices v 4 , v 3 , v, v 1 , v 1 , v 2 , u, and u 1 are colorable by Figure 5xi.

(xvi) We restrict w by one color to color w 1 , w 2 , and w 3 last. We color u with x ∈ L(u) \ L(u 1 ). Observe that L(u 2 ) ⊆ L(u 1 ) so x / ∈ L(u 1 ) ∪ L(u 2 ). We color u 2 and u 1 in this order. We color

, w, and w 1 by Figure 5xi. Now, we color the remaining vertices u 1 and u 2 in this order.

. We color w 2 , w 1 , v 4 , and v 3 in this order. We color

. Now, we color the remaining vertices v 1 , v 2 , w 1 and w 2 in this order.

(xviii) We restrict w by one color to color w 1 , w 2 , and

. We color w, v 4 , and v 3 in this order. We color

. Now, we color the remaining vertices v 1 and v 2 in this order.

(xix) We restrict w by one color to color w 1 , w 2 , and w 3 last. We restrict u by one color to color u 1 , u 2 , and u 3 afterwards. We color u and w then the remaining vertices

, and L(v 4 ) ⊆ L(v 3 ).

Discharging rules

In this section, we will define a discharging procedure that contradicts the structural properties of G (see Lemmas 11 to 13) showing that G does not exist. We assign to each vertex u the charge µ(u) = 19 2 d(u) -21 and to each face f the charge µ(f ) = d(f ) -21. By Equation (1), the total sum of the charges is negative. We then apply the following discharging rules:

Verifying that charges on each face and each vertex are non-negative

Let µ * be the assigned charges after the discharging procedure. In what follows, we will prove that:

First of all, since G is connected (Lemma 9), has minimum degree at least 2 (Lemma 10), has girth at least 21, and the discharging rules do not interfere with charge on faces, every face

Now, let u be a vertex in V (G). If d(u) = 2, then u receives charge 1 from each endvertex of the path it lies on by R3; thus we get µ * (u) = µ(u) + 2 • 1 = 19 2 • 2 -21 + 2 = 0. From now on, suppose that d(u) = 3 and let u = (k, l, m). Recall that µ(u) = 19 2 • 3 -21 = 15 2 : Case 1: Suppose that k + l + m ≥ 8. First, observe that u only gives away charges by R3. More precisely, u gives a total of k + l + m to 2-vertices. Since there are no 6 + -paths, (1 + , 4 + , 5 + ), (2 + , 3 + , 4 + ), or (3 + , 3 + , 3 + ) due to Lemma 11, then the only possible values for k, l, and m are as follows:

• If u is a (5, 5, 0), (5, 4, 0), (5, 3, 0) or (4, 4, 0), then u cannot be adjacent to a vertex v = (m, n, p) with m + n + p ≥ 8 as (430 -024) is reducible by Lemma 12(i). As a result, u receives charge 5 2 (resp. 3 2 , 1 2 , or 1 2 ) by R0(i) (resp. R0(ii), R0(iii), or R0(iii)) when it is a (5, 5, 0) (resp. (5, 4, 0), (5, 3, 0), or (4, 4, 0)). To sum up, we have ) by R2(i) (resp. R2(iii)) when it is a (5, 2, 2) (resp. (4, 2, 2)) twice (once from each incident 2-path). To sum up, we have

• If u is a (3, 3, 2), then u cannot share a 2-path with a vertex v = (m, n, p) with m + n + p ≥ 8 as (412 -233) and (332 -233) are reducible respectively by Lemma 12(vi) and (vii). As a result, u receives charge 1 2 by R2(ii). To sum up, we have

• If u is a (5, 2, 1), then u cannot share a 2-path with a vertex v = (l, i, j) with l + i + j ≥ 8 and u cannot share a 1-path with a vertex w = (m, n, p) with m + n + p ≥ 8 at the same time, as (412 -233) and (421 -132 -214) are reducible respectively by Lemma 12(vi) and Lemma 13(xiv). As a result, u receives at least charge 1 2 by R1(ii) or R2(ii). To sum up, we have

• If u is a (0, 5 -, 2), then we distinguish the four following cases:

If l = 2, then u gives 2 + 3 4 along the 2-path by R3 and R2(i). Since (550 -022 -224) is reducible by Lemma 13(v), v cannot be a (5, 5, 0). As a result, u gives at most 3 2 to its adjacent 3-vertex by R0 and 2 + 3 4 along each 2-path by R3 and R2. So at worst, we have

If l = 3, then u gives 3 along the l-path and 2 along the 2-path by R3.

-If v is a (5, 4 + , 0), then w cannot be a (2, 1 + , 4 + ) nor a (2, 3, 3) as (540-032-214) and (540-032-233) are reducible respectively by Lemma 13(vi) and Lemma 13(vii). As a result, u gives at most 5 2 to v by R0 and nothing to w by R2. So at worst, we have

-If v is not a (5, 4 + , 0), then u gives at most 1 2 to v by R0 and at most 3 4 to w by R2. So at worst, we have

If l = 4, then u gives 4 along the l-path and 2 along the 2-path by R3. Since (430 -024) is reducible by Lemma 12(i), v cannot be a (4 + , 3 + , 0). As a result, u gives at most 1 4 to v by R0 and at most 3 4 to w by R2. So at worst, we have

If l = 5, then u gives 5 along the l-path and 2 along the 2-path by R3.

-If v is a (4 + , 2 + , 0), then w cannot be a (2, 1 + , 4 + ) nor a (2, 3, 3) as (420 -042 -214) and (420 -042 -233) are reducible respectively by Lemma 13(viii) and Lemma 13(ix). Moreover, v cannot be a (4 + , 3 + , 0) since (430 -024) is reducible by Lemma 12(i). As a result, u gives at most 1 4 to v by R0 and nothing to w by R2. So at worst, we have

-If v is not a (4 + , 2 + , 0), then v = (i, j, k) with i + j + k ≤ 7. Thus, u receives 1 4 from v by R0(iv). Moreover, u gives nothing to v by R0 and at most 3 4 to w by R2. So at worst, we have

• If u is a (1, 5 -, 1), then we distinguish the three following cases:

If l = 2, then u gives 2 + 3 4 along the 2-path by R3 and R2(i) and 1 to each 2-vertex on the 1-paths by R3. Since (431 -112 -224) is reducible by Lemma 13(xii), v cannot be a (4 + , 3 + , 1). The same holds for w. As a result, u gives at most 1 2 twice to v and w by R1. So at worst, we have

If l = 3, then u gives 3 to the l-path and 1 to each 2-vertex on the 1-paths by R3. Since (431 -131 -124) is reducible by Lemma 13(x), v and w cannot both be (4 + , 3 + , 1)s. As a result, u cannot give 3 2 twice by R1. So at worst, we have

If 4 ≤ l ≤ 5, then u gives at most 5 along the l-path, 1 to each 2-vertex on the 1-paths by R3. Since (431 -114) is reducible by Lemma 12(iii), u cannot give more than 1 2 to v nor w by R1. Moreover, since (421 -141 -124) is also reducible by Lemma 13(xi), u cannot give 1 2 twice by R1. So at worst, we have

• If u is a (1, 5 -, 2), then l ≤ 4 since k + l + m ≤ 7. Thus, we distinguish the three following cases:

If l = 2, then u gives 2 + 3 4 along at least one of the 2-paths by R3 and R2(i) and 1 to each 2-vertex on the 1-path and other 2-path by R3. Since (431 -112 -224) is reducible by Lemma 13(xii), v cannot be a (4 + , 3 + , 1). As a result, u gives at most 1 2 to v by R1 and at most 3 4 to w by R2. So at worst, we have

If l = 3, then u gives 3 along the l-path and 1 to each 2-vertex on the 1-path and 2-path by R3.

-If v is a (4 + , 2 + , 1), then w cannot be a (2, 1