Quentin Dabouis

Université François Rabelais

ENGLISH STRESS AND UNDERLYING REPRESENTATIONS

This paper addresses the issue of underlying representations (URs) from a Guierrian perspective and the necessity of taking into account certain orthographic elements which are associated with phonological behaviours related to English stress. We propose that underlying vowels should be represented as abstract phonological objects and that the inclusion of orthographic consonant geminates and final mute <e> into URs should be considered. Additionally, we argue that the phonology should have access to morphosyntactic information, which implies that the input to the phonology should be polystratal. Eventually, after arguing that vowel reduction should occur after stress assignment, we will report the results of studies on vowel reduction and "stress preservation" showing that reduction is not systematic in unstressed syllables and that nonreduction can, in some cases, be attributed to the existence of a full vowel in a morphologicallyrelated word or to a high frequency of the latter.

Wells's Longman Pronunciation Dictionary (LPD). These dictionaries, even though not without some mistakes, allow us to access vast amounts of words that could be judged representative of the language 2 . The varieties described in these dictionaries are the standard ones (Received Pronunciation and General American), and the approach presented here does not claim that what is true for these varieties of English is true for all varieties. However, Martin (2011) conducted an intervarietal study of over 3,500 words known to be unstable in RP (e.g. with stress variants or belonging to classes which have numerous exceptions) and found that in over 90% of cases, the position of stress was the same in RP, GA and SAusE (Standard Australian English). Therefore, it seems that English, at least in Kachru's "Inner Circle" (1992), is very stable in its stress system.

) have also used frequency information from the Corpus of Contemporary American English to address the problem of rare or specialised vocabulary by excluding low-frequency items.

Introduction

In most rule-based or constraint-based approaches in phonology, we are faced with the problem of URs and their content. In the approach introduced by Guierre, this problem has never been treated extensively even though the large corpus studies which have been conducted should allow us to address that problem within the approach itself, but also to bring elements of reflection with a more general reach. First, a presentation of the Guierrian School will be given along with an essential distinction to be made between studying individual speakers and studying a language. After giving the arguments in favour of the choice of the latter, a few problems in relation to the role of orthography in English phonology will be addressed along with two additional questions closely linked with English stress: the interface with morphology and vowel reduction.

The Guierrian School

The "Guierrian School" is an approach which was introduced in the seventies by the French researcher Lionel Guierre. During the sixties, Guierre computerised Daniel Jones's pronouncing dictionary and put together one of the largest corpora on English pronunciation at the time (35,000 words). He then studied it in its entirety. His PhD thesis (1979) was presented as an answer to Chomsky and Halle's Sound Pattern of English (1968, hereafter SPE), and his main critique regarding SPE was the absence of any empirical data backing up the rules formulated. Therefore, using this corpus, he tested the efficiency of the rules of stress placement and vowel pronunciation proposed in SPE and found that many rules were not very efficient when tested empirically.

However, Guierre never held that the rules he proposed were to be found in any given native speaker of English's phonology since his object of study was the English language. Unlike SPE's authors who quickly abandoned it, Guierre made an extensive use of the written form of words and included strictly orthographic elements such as consonant geminates, final mute <e> and vowel diagraphs in the parameters conditioning stress placement and vowel value. If Guierre had a few ideas on which of these elements were to be included in a lexical (or underlying) representation, many of the researchers following his work (e.g. Deschamps, Fournier, Trevian) did not all agree on these. However, Deschamps (1983) argued that English orthography is phonological. However, all agree that English phonology is strongly influenced by morphology, and we should consider how to include morphological information in URs as well. To sum up, the Guierrian approach is mainly characterised by the study of pronouncing dictionaries' data and the use of orthography when necessary.

This paper is an attempt to present some of these elements and the arguments that may or may not lead to including them in URs. The notation used in this paper is the one used by all authors working within the approach introduced by Guierre, which is the following:  Angle brackets are used for orthography (e.g. <original>)  Square brackets are used for phonetics (e.g. [əˈrɪdʒɪnəl])  Slashes are used for phonology (e.g. / ? / ) Before investigating the contents of URs, it is necessary to specify the object of study, and more precisely "whose" URs are treated here.

Speaker VS Language

When one studies a phenomenon like English stress, it seems appropriate to define what is being studied exactly and if the aim is to study the language or individual speakers, as the means of investigation will be defined accordingly. Both options present some problems, a few of which are laid down below: Speaker:

 How can we pick an "ideal", "average" or "representative" speaker?  What tests should be used in order to get quality data?  How can we get enough data so that it can be considered representative of a given speaker's phonology?

Language:

 How can we define the English language and its boundaries?  What data should be used?  Should it take into account the relative stratification of the language (e.g. items' frequencies, specialised lexical fields, learned vocabulary)?

Although we can assume that some rules found in a given speaker's phonology may be found in the language, it may not necessarily be the case, so it does not seem reasonable to say that what we find to be true for a given speaker will hold for the language as well, and vice versa.

One of the main characteristics of the Guierrian School is, as mentioned above, to have chosen to study the language1 . Even though defining the language might be difficult, we will follow Saussure's definition:

"It is both a social product of the faculty of speech and a collection of necessary conventions that have been adopted by a social body to permit individuals to exercise that faculty. " (1916: 25) In order to try and study the language, the choice has been made to analyse pronouncing dictionaries like Jones's Cambridge English Pronouncing Dictionary (hereafter CEPD) or Thus, when one is using this methodology, it is possible to study a given class of words by analysing all the items of that class which can be found in the dictionaries. Then, it is possible to give the productivity of a class, the efficiency of the rule applying to it (if any) and the list of exceptions to the rule at stake. With such an inductive approach, formulating rules becomes a question of statistics as well as conventional analysis: a rule can only be called a rule if its efficiency is around 90%. If a phenomenon occurs in 70-90% of cases, we will be talking about a tendency, and under that figure we will be talking about chance. For example, [START_REF] Descloux | Structure, Variation, Usage & Corpora: The Case of Word Stress Assignment in Disyllabic erbs[END_REF] The figures in this table show that the usually assumed rule that dissyllabic verbs are stressed on their second syllable is not a rule at all as they are almost equally divided between early stress and late stress. However, the criterion which seems to be crucial here is prefixation, and we can formulate the rule "prefixed verbs are late-stressed" as it is the case in 93% of cases. Additionally, we could say there is a tendency for suffixed dissyllabic verbs to be earlystressed but, as English suffixes tend to have idiosyncratic properties, the latter should be studied individually and not only within this inventory.

When we choose to study the language, we have access to two forms: the phonetic and the orthographic forms. To determine the contents of URs, we can draw from both accessible forms and them only, as doing otherwise would imply including elements in the representation which cannot be justified but by the theory itself. This reproach was indeed often made to SPE in the case of words like right or nightingale which would present an underlying velar fricative /x/ never attested on the surface explaining the pronunciation of their stressed vowels.

Moreover, psycholinguistic concerns such as the balance between computation and lexical storage, sometimes called "the division of labour" (Bermúdez-Otero & McMahon, 2006), which are essential when one is trying to model individual speakers' phonologies, are irrelevant here. Obviously, the chosen form of representation is determined by the nature of the rules or constraints which will be applied in order to derive the surface representation. For that matter, the rules to keep in mind here are the ones described by [START_REF] Fournier | From a Latin syllable-driven stress system to a Romance vs Germanic morphology-driven dynamics[END_REF]Fournier ( , 2010b)), which could be adapted into rule-based or constraint-based models.

Sketching Empirically-Based Underlying Representations

In this section, we will start with a presentation of the proposed representation of vowels, with three main points:

 vowels can be grouped in series which relate to the same orthographic vowel;  there can be more phonological vowels than there are phonetic vowels (in a word);  we cannot ignore the behaviour of words with final mute <e>.

Then we will tackle the main problem between orthography, phonology and phonetics with regards to consonants: written consonant geminates (e.g. <bb>, <rr>, <mm>).

Eventually, we will deal with the question of the interface with morphosyntax, as several morphosyntactic elements are needed in the representation to derive stress.

One principle to keep in mind during the following paragraphs and that we will adopt here is what Guierre (1979: 33) called the "uniqueness of lexical forms" (in French: "unicité des formes lexicales"). According to that principle, having two possible pronunciations for a same lexical unit does not entail that we must have one lexical form for each of them. For Guierre, controversy

([ˈkɒntrəvɜːsi] 3 ~ [kənˈtrɒvəsi]) or albino ([aelˈbiːnəʊ] (GB) ~ [aelˈbaɪnoʊ] (US))
have only a single lexical form, and the "least bad" known representation of that form is the orthography (Ibid.).

Vowels

Series and their Representation

If we have a look at the following table4 taken from Fournier (2010b: 98), we can see that each written vowel can have:

 four5 different values when it is a monograph (e.g. r-coloured, checked, free and rcoloured free);  two different values when it is a diagraph (e.g. free and r-coloured free). (summed up in Fournier 2010b: 141) determine which value a written vowel is going to have in a given context. If we take the orthography into account, it is easy to see that these vowels are related, but it does not mean that such a relationship has a phonological status7 .

V r

Monographs

However, morphologically-related pairs with vowel alternations seem to go in that direction:

(

1) ~ <divine> [dɪˈvaɪn] ~ <divinity> [dɪˈvɪnəti] <profane> [prəˈfeɪn] ~ <profanity> [prəˈfaenəti] <serene> [səˈriːn] ~ <serenity> [səˈrenəti] V r ~ <isobar> [ˈaɪsəʊbɑː] ~ <isobaric> [ˌaɪsəʊˈbaerɪk] <fluor> [ˈfluːɔː] ~ <fluoric> [fluˈɒrɪk] 8 <scar> [ˈskɑː] ~ <scarify> [ˈskaerɪfaɪ] r ~ <barbarian> [bɑːˈbeəri_ən] ~ <barbaric> [bɑːˈbaerɪk] <empire> [ˈempaɪə] ~ <empiric> [ɪmˈpɪrɪk] <compare> [kəmˈpeə] ~ <comparative> [kəmˈpaerətɪv]
It seems that these alternations have a status in the language independently of the orthography. Another type of alternation needs to be taken into account before we can formulate a proposition for the representation of vowels: the alternation between "foreign vowels" and "indigenous vowels".

Foreign Vowels

Another of Guierre's arguments to postulate underlying vowels equivalent to orthographic vowels is the alternation between foreign9 free vowels ( e ) and indigenous 10 free vowels ( ).

We can find three main foreign vowels:

e <a> [eɪ] [ɑː] <e> [iː] [eɪ] <i> [aɪ] [iː]
Table 3. Indigenous and foreign free vowels Approaches which do not take into account the orthography usually do not have a concept of "foreign vowels", for phonetically the latter belong to the set of English vowels. What actually makes them "foreign" is precisely their relationship with the orthography, and following our proposition here, with their UR. When words containing these vowels get "naturalised" (i.e. adapted to the indigenous phonological system), the changes in pronunciation are highly predictable, especially the indigenous vowel which is going to be chosen, as in:

(

2) <albino> [aelˈbiːn əʊ] (GB) ~ [aelˈbaɪnoʊ] (US) <tomato> [təˈmɑːtəʊ] (GB) ~ [təˈmeɪt oʊ] (US)
In these examples, we can see that British English has preserved a "foreign" pronunciation whereas American English has adapted these words to its phonological system by adapting the vowels:

[iː]  [aɪ] ; [ɑː]  [eɪ].
Of all the values they could take, the vowels change to the indigenous vowel corresponding to the same orthographic vowel. This could be seen as a simple influence of orthography, but Guierre argued that it was because the two values found in these words (foreign and indigenous) relate to the same underlying vowels, in the case of the words in (2), /i/ and /a/.

We will not go as far as claiming that it is so, for it would imply to attribute features to these vowels, and we would require synchronic rules for the Great Vowel Shift, such as the Vowel Shift Rule (discussed in [START_REF] Mcmahon | Who's afraid of the vowel shift rule?[END_REF]. The idea is not to say that all values derive from the same underlying vowel through various alterations, but only to say that they are related, and that they share a common quality. Therefore, the representation for vowels proposed here is one that refers to abstract objects representing a series of surface vowels, and these abstract objects do not have any phonological content. It is only the context in which these objects occur which is going to determine which value is going to surface. We can find series of minimal pairs with vowels having the same value but only differing by their quality (e.g. pat, pet, pit, pot, put for checked vowels; mate, mete, mite, mote, mute for free vowels). As far as notation is concerned, the option favoured here is that of using the orthographic symbols for these abstract objects (e.g. /e/ would represent the series [ɜː], [e], [iː], [ɪə] (+ foreign [eɪ])) but we could very well adopt other notations (e.g. V e ). The choice of the representation is potentially debatable, but is of secondary importance here.

Diagraphs

There are two environments in which vowels are usually short, unless they are represented by a diagraph:

-Before a consonant cluster or before the final consonant of a word:

(3) <auction> [ˈɔːkʃən] ~ <action> [ˈaekʃən] <seat> [ˈsiːt] ~ <sit> [ˈsɪt]
-When they are found in the antepenultimate syllable11 :

(4) <speechify> [ˈspiːtʃɪfaɪ] ~ <specify> [ˈspesəfaɪ]
Diagraphs could be represented by their orthographic form as well to refer to the reduced series that they represent (free vowels and r-coloured free vowels; e.g. /ee/ would represent the series [iː], [ɪə]). Another to formalise their behaviour could be to say that they function as diacritics of length, as the vowels they represent are usually long.

Synaeresis

There are words for which the count of vowels (and thus syllables) is different between the orthographic and phonetic forms, as in ocean and partial, which both have three orthographic vowels but only two phonetic vowels, as two vowels got historically compressed and reduced into one under synaeresis. However, these words exhibit an interesting behaviour when derived:

(

5) <ocean> [ˈəʊʃən]  <oceanic> [ˌəʊʃiˈaenɪk] <partial> [ˈpɑːʃəl]  <partiality> [ˌpɑːʃiˈaeləti]
In their derivatives, oceanic and partiality, the two vowels that were compressed into one are distinct as the strong suffixes -ic and -ity entail the placement of primary stress on the second syllable of the two. This leads us to think that there are not two but in fact three phonological vowels in ocean and partial, and that it is a reduction phenomenon which causes the last two to be compressed into one. In general, we consider that there are as many syllables as there are orthographic vowels12 except in two cases:

 Vowel diagraphs, as they represent only a single vowel (e.g. <ea>: sea ≠ react);  Final mute <e>, which will be examined below.

Final Mute <e>

Final mute <e> is well-known by English native speakers, for they learn about its special behaviour with regards to the vowel preceding it, so that it is sometimes called "magic e" by teachers who teach reading and writing. It constitutes what Guierre called a "tensing context", i.e. a context in which vowels are "tense"13 when they are stressed or unreduced14 . We could write down the rule for final mute <e> as follows.

(6) V / __C 1 e

Examples in (7) illustrate this behaviour under stress, those in (8) when the vowel is unstressed and unreduced, and those in (9) when reduction is optional. Orthographically, this rule can be extended to all vowels in this context, and can be formulated as in (10). Examples illustrating that rule are listed in ( 11).

( ˈbaby, biˈkini, ˈcoma, koˈala, ˈphoto, torˈpedo, volˈcano, … In this context, final mute <e> functions as a vowel, which is not very surprising for it was once pronounced [START_REF] Bermúdez-Otero | Prosodic optimization: the Middle English length adjustment[END_REF][START_REF] Duffell | A New History of the English Metre[END_REF][START_REF] Minkova | The environment for open syllable lengthening in Middle English[END_REF], 1991) and the rule in ( 10) was not an orthographic rule at the time. However, it functions mostly as a diacritic.

) V  / __C 1 V# (11) aˈroma, 10
It should be noted that it never counts as a syllable when it comes to stress assignment. This is shown by the stress patterns in non-derived words of three syllables or more15 , which are subject to the Normal Stress Rule (NSR), when they are not prefixed non-substantives16 .

(12) Normal Stress Rule 17

Words of three syllables or more are stressed on their penultimate syllable.

As illustrated by the following examples, final mute <e> never counts as a syllable:

(13) ˈenvelope ; ˈparadise ; (and not *enˈvelope ; *paˈradise) Thus, final mute <e> seems to have a status in the language both through the phonological behaviours associated with its presence and simply through its existence in one of the two forms we have access to (in this case, the orthography). The question of its representation at the underlying level leaves two possible options. Either we can represent it:

 As the vowel /e/, which would have the same properties than other vowels overall but would have the specificity of being erased before stress assignment when found in final position. This could either be done by a deletion rule in a rule-based model or by a constraint forbidding its presence on the surface in a constraint-based model;  As a diacritic, which has the advantage of not including an element in the representation that will need to be erased later in the derivation. However, in doing this we lose the parallelism between the behaviour of final mute <e> and that of other vowels.

As we leave this question open for now, let us turn to another element which presents similar problems: consonant geminates.

Consonant Geminantes

Consonant geminates are the main point of divergence between orthography, phonetics and phonology: they are represented orthographically by a consonant cluster; they behave like one phonologically but always surface as a single phonetic consonant. They are very efficient for the prediction of stress placement and vowel pronunciation:

(14) oˈ , aˈn a, ˌc aˈ , ˈn (≠ ˈno ), ˈ (≠ ˈ ), ˈ o
As pointed out by [START_REF] Deschamps | L'orthographe de l'anglais est-elle phonologique ?[END_REF], they also explain the behaviour of <u>, usually long when stressed unless it is before a consonant cluster or in a final closed syllable, in words like those in (15) which parallel the behaviour before a consonant cluster, as in ( 16).

(15) butter, mutter, rubber (16) function, pustule, vulture However, like final mute <e#>, all we can observe is a phonological behaviour, not its cause, as they are never pronounced as geminates. Once again, we have two options:

 Represent them as underlying geminates and simplify them later in the derivation;  Represent them with a diacritic indicating their specific behaviour.

Interface with Morphosyntax

In his thesis (1979), Guierre argued against the idea that syllable weight was central in the phonological system of English18 , especially with regards to vowel quality. Vowels are extremely variable according to the context in which they appear, and it seems unreasonable to attribute an underlying value to them 19 . He also warned against potential circular logic which could be derived from that concept, such as SPE's argument that vowels are long because they are stressed and that they are stressed because they are long20 . Guierre argued that if the relationship between vowel length and stress is to be oriented, stress should come first. In fact, he argued that vowel values are determined mostly by the context in which they appear, and that stress allows for the expression of these values whereas reductionwhen it occursobscures them. Thus, for him vowel value and stress assignment could be processed in parallel, and independently21 . Only reduction needs to occur afterwards. However, stress has been shown to be morphologically-influenced, and according to [START_REF] Fournier | Que contraignent les terminaisons contraignantes ?[END_REF], more than what is usually assumed. A very well known phenomenon is that of "strong suffixes", more often called "Class I suffixes" [START_REF] Spencer | Morphological Theory: An Introduction to Word Structure in Generative Grammar[END_REF], as opposed to stress-neutral suffixes, "Class II suffixes"22 . Here are a few examples:

(17) Class I: -ion, -ity, -ic, -a ,… Class II: -ness, -less, -hood, -ful, -y,…

This difference could be formally represented the way it is represented in Lexical Phonology [START_REF] Kaisse | On the Theory of Lexical Phonology[END_REF][START_REF] Kiparsky | From Cyclic to Lexical Phonology[END_REF] or, more recently, in Bermúdez-Otero's version of Stratal OT (2012), with Class I rules applying at the "stem-level" and Class II rules applying at the "word-level"23 , even though it would require some adaptations 24 .

In the Guierrian approach, the main parameter conditioning English phonology is thought to be morphology, and semantically-defined morphological domains. Different morphological units behave differently phonologically, thus the notion of morphologically-defined phonological domain is definitely relevant. URs should then include information relative to these morphologically-defined phonological domains, which we could represent with labelled brackets corresponding to the different strata, such as that which can be found in many generative works, like the following examples for regarding and classifiable:

(18) [ w [ s re+gard] s iŋ] w [ w [ s [ s class] s ifi] s able] w
(W: word level; S: stem level) Additionally, as illustrated by the rule concerning prefixed non-substantives, information about syntactical categories is necessary for stress assignment. Thus, we could use another labelled bracketing in order to display that information: To sum up, when it comes to English phonology, we need information from other linguistic levels (or modules) 25 , and that requires that the input to the phonology should contain all that information. Therefore, the input would have to be polystratal. The details concerning the contents or the number of these strata are, however, well beyond the scope of this paper.

(19) [ V [ V [ P re] P [ R gard] R ] V iŋ] V [ A [ V [ N class] N ifi] V able

Vowel Reduction

If we consider vowel values to be predictable by the context in which vowels appear, we need to mention cases in which that value is not expressed, e.g. when reduction occurs26 . Reduction is usually seen as the "norm" in unstressed syllables, especially those adjacent to primary stress. A recent PhD dissertation by [START_REF] Dahak | Étude diachronique, phonologique et morphologique des syllabes inaccentuées en anglais contemporain [Diachronic, phonological and morphological study of unstressed syllables in contemporary English[END_REF] showed that this was not the case, as the percentage of unreduced vowels varied considerably according to the syllabic position under scrutiny. As we can see in this table, the highest proportion of reduced vowels is found in post-tonic syllables which are adjacent to the primary-stressed syllable in three or four syllable words. However, the lowest proportion of reduction is found in the middle syllable of a final string of three unstressed syllables.

Some other recent studies [START_REF] Collie | English stress-preservation and Stratal Optimality Theory[END_REF][START_REF] Kraska-Szlenk | Analogy: the relation between lexicon and grammar[END_REF] have shown what are often called "stress preservation"28 effects. Indeed, they have showed that the relative frequency of a base and its derivative had an influence on stress preservation. Indeed, if the derivative is more frequent than the base, then reduction is more likely to occur, and vice versa, as evidenced in Table 5 . Additionally, it was found that, for these words, reduction was more widespread in prefixes than in roots, hinting that different morphological units may have a different "resistance" to reduction, for instance that prefixes tend to reduce more than roots. This second finding is in line with a phenomenon Guierre described in his thesis (1979: 253): initial pretonic vowels followed by a consonant cluster tend to remain unreduced, except when they are monosyllabic prefixes, in which case they massively undergo reduction.

Eventually, one could ask what should be done about the representation of vowels which are always reduced. Precisely because they are always reduced, their quality can never be accessed phonetically. Guierre argued that if one should form a new word like *cymbalic, it would most likely be pronounced [sɪmˈbaelɪk], even though in cymbal, the second vowel is completely reduced. In that case, -ic predicts the position of stress and the value of the stressed vowel (checked), but it is the orthography which provides the vowel quality (<a>). Without the orthography, any checked vowel could be used, but the orthography determines which one is to be chosen29 .

Conclusion

We have argued in favour of an abstract UR of English vowels to account for a variety of surface alternations. The choice of such a representation raises the question of the abstractedness of URs. We believe that abstract forms can be justified if they can be supported by phonological or orthographic evidence and that they need not have any phonological content as long as they are distinctive. Vowel diagraphs, consonant geminates and final mute <e> could all be formalised as diacritics or in a form close to orthography. However, the choice between these two options seems futile as both imply added lexical information. We would personally favour the second option, as it would be closer to one of the two accessible forms. Furthermore, we have proposed that the input to the phonology should contain information from other linguistic levels and should therefore be polystratal. Eventually, we discussed the issue of vowel reduction, the view that the latter obscures the quality of vowels and the idea that this quality could potentially be maintained by the existence of morphologically-related word in which it is not obscured. To conclude, it seems difficult to study English phonology with no reference to orthography and the latter should probably be taken into account more often. Some arguments were presented to demonstrate an influence of orthography in the language, such an influence can also be found when studying individual speakers, as in Taft's psycholinguistic experiments (2006) seem to show.

  fat) ; bite (≠ bit) ; cote (≠ cot) ; ~ ɪ] ; ˈadvocate[eɪ ~ ə]

  ] A (P: prefix; V: verb; A: adjective; N: noun; R: root)

Table 1 .

 1 Stress in dissyllabic verbs (from[START_REF] Descloux | Structure, Variation, Usage & Corpora: The Case of Word Stress Assignment in Disyllabic erbs[END_REF]

	looked at over 2,500 dissyllabic verbs and found the following stress
	patterns:
		Early Stress Nb %	Late stress Nb %	Total
	Suffixed	177	74%	63	26%	240
	Compounds	245	85%	44	15%	289
	Prefixed	92	7%	1170	93%	1262
	Bases	673	89%	85	11%	758
	Total	1187	47%	1362	53%	2549

Table 4 .

 4 Percentage of non-reduction in unstressed syllables according to the syllabic rank27

	Syllabic rank	% of non-reduced vowels
	100	3.4%
	1000	5.1%
	-201-	22.2%
	-10	26.6%
	10	33.9%
	-1000	53.6%

Table 5 .

 5 Stress preservation and frequency (from[START_REF] Bermúdez-Otero | The Architecture of Grammar and the Division of Labour in Exponence[END_REF]: 32, after Kraska-Szlenk 2007: §8.1.2) We found a similar effect in[START_REF] Abasq | Stress in Dissyllabic erb/Noun Pairs[END_REF] and showed that, in dissyllabic prefixed noun/verb pairs (e.g. record, concern, process), vowel reduction is less likely to occur if there exists a stress variant in which that vowel bears stress, i.e. there are more chances of having the noun record pronounced [ˈrekɔːd] than [ˈrekəd] because of the existence of the verb pronounced[riˈkɔːd]

	below.

Even though the study of individual speakers is not excluded, it is just seen as distinct. Some Guierrian studies have already done tests on speakers(Martin,

2011) and more will most likely come.

[START_REF] Collie | English stress preservation: the case for "fake cyclicity[END_REF] calls the language described in CEPD "an artificial idiolect of English".

All the phonemic transcriptions given in this paper are British pronunciations taken from LPD, unless indicated otherwise.

This table concerns only stressed vowels, so it does not include reduced vowels.

That does not include foreign vowels, see §4.1.2.

For example, the rule given in (10) or the rule associating words in -ic with a short vowel both have an efficiency of over 95%.

As I am concerned here with the language, I will not argue for or against the reality of such vowels for English speakers. For a review on the study of vowel alternations, see[START_REF] Eddington | Surface analogy and spelling rules in English vowel alternations[END_REF].

This is the British pronunciation according to LPD. According to that same dictionary, American English has two possible pronunciations: [fluˈɔːrɪk] ~ [fluˈɑːrɪk], the first one respecting isomorphism with the base.

"Foreign vowels" are the ones which imitate the pronunciation of these vowels in the language from which the words usually containing these vowels are borrowed.

This phenomenon is usually known as Trisyllabic Shortening/Laxing, but Guierrian authors usually talk about "Luick's rule"[START_REF] Luick | Beiträge zur englischen Grammatik III. Die Quantitätsveränderungen im Laufe der englischen Sprachentwicklung[END_REF], who first described the phenomenon.

However, syllabic consonants (as in words in <Cm#>, <Cle#>, <Cre#>) are never counted as a phonological syllable, even though they can constitute a phonetic syllable.

Guierre considered all the values given in Table2except to be "tense". However, in the case of final mute <e>, it concerns only , e and r .

Not all authors agree on the possibility for vowels to be unstressed and unreduced as they consider that vowel length is always associated to some level of stress (secondary or tertiary). For Guierre, this need not be the case, and he refuted the existence of stresses after primary stress (this view could be supported by the phonetic study byPlag & Kunter, 2011, who found that pre-tonic secondary stress was phonetically indistinguishable from primary stress, whereas it is not the case for post-tonic secondary stress).

Here the syllable count does not include <e>.

Indeed, prefixed non-substantives have a different behaviour: their prefixes are ignored when it comes to stress assignment[START_REF] Fournier | From a Latin syllable-driven stress system to a Romance vs Germanic morphology-driven dynamics[END_REF]. An example of the behaviour can be seen in the study on verbs reported in Table1.

So did Fournier, 2010b.

Except maybe in the case of vowels which are represented by diagraphs, which are almost always long.

This logic is still found in more recent articles, as in[START_REF] Duanmu | Onset and the Weight-Stress Principle in English[END_REF], where we can read: "Stressed syllables are heavy/Heavy syllables are stressed".

However, this view is not shared by all authors who worked after him. For Fournier, one can predict the value of a vowel efficiently only when that vowel is bearing stress. In other terms, vowel value comes only once stress assignment has taken place.

Even though the definition Fournier gives of strong suffixes is not exactly equivalent to the common assumptions about Class I suffixes, for more details, see[START_REF] Fournier | Que contraignent les terminaisons contraignantes ?[END_REF].

The assignment of a given suffix to a given level is seen as an idiosyncratic property of that suffix.

For example, it seems problematic to include both non-derived words and words containing Class I suffixes in the stem-level when only the former are subject to the rule described in note 16. Additionally, the concept of "fake cyclicity" proposed by[START_REF] Collie | English stress preservation: the case for "fake cyclicity[END_REF] afterBermúdez-Otero & McMahon (2006) and Bermúdez-Otero (in preparation) seems adapted to capture the relationships of isomorphism between morphologically-related words, especially the idea that the whole form of an embedded word is accessible to the phonology to derive the surface form of a related embedding word, which is an idea that is usually assumed by Guierrian authors.

Which can itself be conditioned by yet other linguistic levels, as when semantics condition morphological boundaries (e.g. reform ~ re-form  one unit versus two units, semantic and morphological).

Reduction is seen here as resulting from stress.

The figures 1, 2 and 0 between slashes are commonly used by Guierrian authors to represent stress patterns: /1/ stands for primary stress, /2/ for secondary stress and /0/ for unstressed syllables. Therefore, the stress pattern of ˌcigaˈrette can be represented as /201/.

However, within the framework presented here this phenomenon would be described in terms of non-reduction of unstressed vowels in related derivatives.

For this example, phonological priming would of course exclude [sɪmˈbɒlɪk] (i.e. symbolic), but not [sɪmˈbelɪk] nor even [sɪmˈbʌlɪk].

Acknowledgements

We are grateful to J.-M. Fournier, M. Martin, M. Cotton-Kinch and two anonymous reviewers for their corrections and constructive comments. Responsibility for any mistakes or omission is mine alone.


Frédéric Havet
email: frederic.havet@inria.fr

Andrew D King

Mathieu Liedloff

Ioan Todinca

Pavol Hell

(Circular) backbone colouring: forest backbones in planar graphs

Consider an undirected graph G and a subgraph H of G, on the same vertex set. The qbackbone chromatic number BBC q (G, H) is the minimum k such that G can be properly coloured with colours from {1, . . . , k}, and moreover for each edge of H, the colours of its ends differ by at least q. In this paper we focus on the case when G is planar and H is a forest. We give a series of NP-hardness results as well as upper bounds for BBC q (G, H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.

Introduction

All the graphs considered in this paper are simple. Let G = (V, E) be a graph, and let H = (V, E(H)) be a spanning subgraph of G, called the backbone. A k-colouring of G is a mapping f : V → {1, 2, . . . , k}. Let f be a k-colouring of G. It is a proper colouring if |f (u) -f (v)| ≥ 1 for all edges uv ∈ E(G). It is a q-backbone colouring for (G, H) if f is a proper colouring of G and |f (u) -f (v)| ≥ q for all edges uv ∈ E(H). The chromatic number χ(G) is the smallest integer k for which there exists a proper k-colouring of G. The q-backbone chromatic number BBC q (G, H) is the smallest integer k for which there exists a q-backbone k-colouring of (G, H).

If f is a proper k-colouring of G, then g defined by g(v) = q • f (v) -q + 1 is a q-backbone colouring of (G, H) for any spanning subgraph H of G. Moreover it is well-known that if G = H, this q-backbone colouring of (G, H) is optimal. Therefore, since BBC q (H, H) ≤ BBC q (G, H) ≤ BBC q (G, G), we have q • χ(H) -q + 1 ≤ BBC q (G, H) ≤ q • χ(G) -q + 1.

(

) 1
If H is empty (i.e. E(H) = ∅), then BBC q (G, H) = χ(G). Hence for any k ≥ 3, deciding if BBC q (G, H) ≤ k is NP-complete because deciding if a graph is k-colourable is NP-complete (See [START_REF] Garey | A guide to the theory of NP-completeness[END_REF]). However, when we impose G or H to belong to certain graph classes, the problem sometimes become polynomial-time solvable. A trivial example is when we consider H with chromatic number at least r > (k + q -1)/q. Then BBC q (G, H) ≥ rq -q + 1, and so deciding if BBC q (G, H) ≤ k can be done instantly by always returning 'no'. A less trivial example is when we impose H to have minimum degree 1. For such an H, deciding if BBC q (G, H) ≤ q + 1 is also polynomial-time solvable, because BBC q (G, H) = q + 1 if and only if G is bipartite. This simple observation was already made by Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] when H is a 1-factor (a spanning subgraph in which every vertex has degree exactly 1). Furthermore, if we also impose H to be connected, we show in Theorem 17 that deciding if BBC q (G, H) ≤ q + 2 can be done in polynomial time. In contrast, if the condition of H being connected is removed, then it is NP-complete (Theorem 18).

In this paper, we will focus on the particular case when G is a planar graph and H is a forest (i.e. an acyclic graph). Inequality [START_REF] Borodin | On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph[END_REF] and the Four-Colour Theorem imply that for any planar graph G and spanning subgraph H, BBC q (G, H) ≤ 3q + 1. However, for q = 2, Broersma et al. [START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF] conjectured that this is not best possible if the backbone is a forest.

Conjecture 1. If G is a planar graph and F a forest in G, then BBC 2 (G, F ) ≤ 6.

If true, Conjecture 1 would be best possible. Broersma et al. [START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF] gave an example of a graph Ĝ with a forest F such that BBC 2 ( Ĝ, F ) = 6. See Figure 1. It is then natural to ask how large BBC q (G, F ) Figure 1: A planar graph Ĝ with a forest F (bold edges) such that BBC q ( Ĝ, F ) = q + 4. could be when G is planar and F is a forest for larger values of q. We prove the following.

Theorem 2. If G is a planar graph and F a forest in G, then BBC q (G, F ) ≤ q + 6.

In fact, we prove a more general result in Proposition 13 : for any pair (G, H) with H a subgraph of G, BBC q (G, H) ≤ (χ(G) + q -2)χ(H) -q + 2.

For q ≥ 4, Theorem 2 is best possible. Indeed, we show a planar graph G * together with a spanning tree T * such that BBC q (G * , T * ) = q + 6 for all q ≥ 4. See Figure 2 and Proposition 15. Furthermore, we show in Theorem 31, that for any fixed q ≥ 4, given a planar graph G and a spanning tree T of G, it is NP-complete to decide if BBC q (G, T ) ≤ q + 5.

On the other hand, we believe that if q = 3, Theorem 2 is not best possible. Figure 2: A planar graph G * and a tree T * (bold edges) such that BBC q (G * , T * ) = q + 6 for q ≥ 4.

A star is a tree in which a vertex v, called the center is adjacent to every other. A galaxy is a forest of stars. As evidence in support of Conjectures 1 and 3, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] showed that if F is a galaxy in a planar graph G, then BBC q (G, F ) ≤ q + 4. This result is best possible even if F has maximum degree 3 as shown by the example of Figure 1. Furthermore, we show in Theorems 21 and 28 that, for any q ≥ 2, it is NP-complete to decide if BBC q (G, F ) ≤ q + 3 given a planar graph G and a galaxy of maximum degree 3.

However, if the backbone is a matching, i.e. a galaxy with maximum degree 1, then fewer colours are needed. Indeed, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] showed that if M is a matching in a planar graph G, then for any q ≥ 3, BBC q (G, M ) ≤ q + 3. They conjectured that the same holds for q = 2.

Conjecture 4 (Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF]). If G is a planar graph G and M a matching in G, then BBC 2 (G, M ) ≤ 5.

It is natural to ask the same question for galaxies with maximum degree at least 2. When q = 2, we answer in the negative by showing that there are pairs of planar graphs and spanning forests of maximum degree 2 whose 2-backbone chromatic number is 6. Furthermore, we show that given a planar graph G and a spanning forest F of maximum degree 2, it is NP-complete to decide whether BBC 2 (G, F ) ≤ 5 (Theorem 22). We also show that given a planar graph G with a hamiltonian path P , it is NP-complete to decide whether BBC 2 (G, F ) ≤ 5. This result refines a result of Broersma et al. [START_REF] Broersma | Backbone colorings for networks[END_REF][START_REF] Broersma | Backbone colorings for graphs: tree and path backbones[END_REF] who proved it for a general graph G.

For q = 3, the problem remains open.

Problem 5. If G is a planar graph G and F a galaxy of maximum degree 2, is is true that BBC q (G, F ) ≤ q + 3, for all q ≥ 3?

Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] proved that deciding if BBC q (G, M ) ≤ q+2 for a given graph G and matching M is NP-complete. We prove in Subection 2.2 that it remains NP-complete even if we impose G to be G planar H forest H spanning tree H 1-factor H Hamilton path BBC q (G, H) ≤ q + 1?

NP-C poly poly poly BBC q (G, H) ≤ q + 2?

NP-C poly NP-C poly BBC q (G, H) ≤ q + 3?

NP-C NP-C q ≥ 3: Yes q = 2: ?Yes? q = 2: NP-C BBC q (G, H) ≤ q + 5?

q ≥ 4: NP-C q = 3: ?Yes? q = 2: Yes BBC q (G, H) ≤ q + 6? Yes Table 1: Complexity of deciding if BBC q (G, H) ≤ q + k for k ∈ {1, . . . , 6}, when G is a planar graph and H a forest of some prescribed classes. NP-C:= NP-Complete; poly:= polynomial-time decidable; Yes: always true; ?Yes? conjectured to be always true.

planar. In contrast, we prove that deciding if BBC q (G, T ) ≤ q + 2 for a given graph G and spanning tree T is polynomial-time solvable.

Many of the complexity results on backbone colouring of planar graphs with a forest backbone are summarized in Table 1.

One can generalize the notion of backbone colouring by allowing a more complicated structure of the frequency space. The most natural one is to consider a circular metric. A circular k-colouring of G or Z k -colouring is a mapping f : V → Z k . The notions of circular q-backbone colouring and circular q-backbone chromatic number are defined similarly to those of q-backbone colouring and circular q-backbone chromatic number by replacing colouring by circular colouring. The circular q-backbone chromatic number of a graph pair (G, H) is denoted CBC q (G, H).

If f is a circular q-backbone k-colouring, then the mapping f * defined by f (v) = f (v) + 1 for all vertex v is trivially a q-backbone k-colouring. On the other hand, a q-backbone k-colouring yields a circular q-backbone (k + q -1)-colouring. Hence for every graph pair (G, H), where H is a spanning subgraph of G, we have

BBC q (G, H) ≤ CBC q (G, H) ≤ BBC q (G, H) + q -1. (2)
Also,

q • χ(H) ≤ CBC q (G, H) ≤ q • χ(G). (3)
Observe that if G is bipartite and H is non-empty, Equation (3) implies that CBC q (G, H) = 2q. More generally, if χ(G) = χ(H), then CBC q (G, H) = q • χ(G). However if 2 ≤ χ(H) < χ(G), one can improve the upper bound. We show in Proposition 32 that, for any pair

(G, H) with H a subgraph of G, CBC q (G, H) ≤ (χ(G) + q -2)χ(H). (4)
Since CBC q (G, H) = χ(G) when H is empty and k-COLOURABILITY is NP-complete, for any fixed k ≥ 3, given a graph G and a subgraph H it is NP-complete to decide if CBC q (G, H) ≤ k. But if insist that H is not empty, then CBC q (G, H) ≥ 2q by Proposition 3. Hence deciding if CBC q (G, H) is at most k with k ≤ 2q -1 can be done instantly by always returning 'no'. Less trivially, Proposition 35 shows that if H is a connected spanning subgraph of G, then CBC q (G, H) = 2q if and only if G is bipartite. Hence deciding if CBC q (G, H) = 2q can be done in polynomial time.

Inequality (4) implies that CBC q (G, F ) ≤ 2q + 4 for any planar graph G and forest F in G. We believe that this upper bound can be reduced by at least one. Conjecture 6. If G is a planar graph and F a spanning forest of G, then CBC q (G, F ) ≤ 2q + 3.

A natural question is to ask whether this conjecture would be best possible. Problem 7. For any q ≥ 2, does there exist a planar graph G q and a spanning forest F q of G q such that CBC q (G q , F q ) = 2q + 3? Conjecture 6 holds if the backbone F is a galaxy. It follows directly from (2) and the fact that BBC q (G, F ) ≤ q + 4 in such a case, as mentioned earlier. We believe however that one can use one colour less.

Conjecture 8. Let G be a planar graph and F a galaxy in G, then CBC q (G, F ) ≤ 2q + 2.

If true, this conjecture would be tight, since the circular q-backbone chromatic number of a K 4 with backbone K 1,3 is 2q + 2. As evidence in support of Conjecture 8, Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] deduced from the Four-Colour Theorem that if G is a planar graph and M a matching in G then CBC q (G, M ) ≤ 2q + 2.

Broersma et al. also give an example of a planar graph G and a matching M such that (G, M ) has no 2-backbone Z 5 -colouring. We show in Theorems 36 and 40 that for any fixed k ∈ {4, 5}, it is NP-complete to decide if BBC 2 (G, M ) ≤ k for given planar graph G and matching M . For larger values of q, the following questions are still open. Problem 9. Let G be a planar graph and let M be a matching M in G. For any q ≥ 3, is it true that CBC q (G, M ) ≤ 2q + 1 ?

Problem 10. Is it NP-complete to decide if CBC 2 (G, F ) ≤ 6 for a planar graph G and spanning forest F ? Problem 11. For any g ≥ 5, is it NP-complete to decide if CBC 2 (G, M ) ≤ 4 for a planar graph G of girth at least g and matching M ?

We prove in Theorem 33 that if G has girth at least 5, then CBC q (G, M ) ≤ 2q + 1. We wonder if the same holds for planar graph of girth 4.

Problem 12. Let G be a planar graph of girth 4 and let M be a matching in G. Is it true that CBC q (G, M ) ≤ 2q + 1 ?

Many of the complexity results on circular backbone colouring of planar graphs with a forest backbone are summarized in Table 2.

2 Backbone colouring 2.1 About Conjectures 1 and 3 Proposition 13. Let G be a graph and let H be a subgraph of G. 4}, when G is a planar graph and H a forest of some prescribed classes. NP-C:= NP-Complete; poly:= polynomial-time decidable; Yes: always true; ?Yes? conjectured to be always true.

Then BBC q (G, H) ≤ (χ(G) + q - 2)χ(H) -q + 2. G planar H forest H spanning tree H 1-factor H Hamilton path CBC q (G, H) ≤ 2q? q=2: NP-C poly q=2: NP-C poly CBC q (G, H) ≤ 2q + 1? NP-C poly q=2: NP-C q=2: NP-C CBC q (G, H) ≤ 2q + 2? CBC q (G, H) ≤ 2q + 3? ?Yes? CBC q (G, H) ≤ 2q + 4? Yes Table 2: Complexity of deciding if CBC q (G, H) ≤ 2q + k for k ∈ {0, . . . ,
Proof. Let g be a proper χ(G)-colouring of G and h a proper χ(H)-colouring of H. Let f be the colouring defined by:

f (v) = (h(v) -1)(q -2 + χ(G)) + g(v), if h(v) is odd, (h(v) -1)(q -2 + χ(G)) + χ(G) + 1 -g(v) if h(v) is even. Let us check that f is a q-backbone ((χ(G) + q -2)χ(H) -q + 2)-colouring of (G, H). Let uv ∈ E(G). Without loss of generality, h(u) ≥ h(v). If h(u) = h(v), then uv / ∈ E(H) and |f (u) -f (v)| = |g(u) -g(v)| = 0.
Assume now that h(u) > h(v). If h(u) and h(v) are both odd or both even, then

f (u) -f (v) ≥ 2(q -2 + χ(G)) -|(g(u) -g(v)| ≥ q. If h(u) is odd and h(v) is even, then f (u) -f (v) ≥ q -3 + g(u) + g(v), which is at least q because g(u) + g(v) ≥ 3 for g(u) = g(v). If h(u) is even and h(v) is odd, then f (u) -f (v) ≥ q -2 + 2χ(G) + 1 -g(u) -g(v), which is at least q because g(u) + g(v) ≤ 2χ(G) -1 for g(u) = g(v).
A parachute on v or a parachute with harness v is a complete graph on four vertices whose three edges incident to v are in the backbone. Proposition 14.

(i) For q ≥ 2, in a q-backbone (q + 3)-colouring of a parachute, the harness is coloured in {1, q + 3}.

(ii) For q ≥ 3, in a q-backbone (q + 4)-colouring of a parachute, the harness is coloured in {1, 2, q + 3, q + 4}.

(iii) For q ≥ 4, in a q-backbone (q + 5)-colouring of a parachute, the harness is coloured in {1, 2, 3, q + 3, q + 4, q + 5}.

Proof. Let y be the harness.

(ii) If 3 ≤ φ(y) ≤ q + 2, then at most two colours can appear on its neighbours. Because those three vertices form a clique, they have three different colours and so φ(y) ∈ {1, 2, q + 3, q + 4}.

(iii) If 4 ≤ φ(y) ≤ q + 2, then at most two colours can appear on its neighbours. Because those three vertices form a clique, they have three different colours and so φ(y) ∈ {1, 2, 3, q + 3, q + 4, q + 5}.

Proposition 15. Let G * and T * be the graph and its spanning tree depicted in Figure 2. For any q ≥ 4, BBC q (G * , T * ) ≥ q + 6.

Proof. Assume for a contradiction that there is a q-backbone (q + 5)-colouring φ of (G * , T * ). By Proposition 14-(iii), the vertices y 1 , y 2 , y 3 , y 4 , z 1 , z 2 are coloured in {1, 2, 3, q + 3, q + 4, q + 5}. Without loss of generaltiy, we may assume that φ(y 2 ) ∈ {1, 2, 3}. But then φ(z 1 ) and φ(z 2 ) must be in {q + 3, q + 4, q + 5}, because y 2 z 1 and y 2 z 2 are in E(T * ). And φ(y 1 ), φ(y 2 ) and φ(y 3 ) are in {1, 2, 3} because y 3 z 1 and y 1 z 2 and y 4 z 2 are in E(T * ). But {y 1 , y 2 , y 3 , y 4 } is a clique in G * , so they must all get different colours, a contradiction.

Proposition 16. Conjecture 1 implies Conjecture 3.

Proof. Assume that Conjecture 1 holds. Let G be a planar graph and F a forest in G. Then (G, F ) admits a 2-backbone 6-colouring φ. Let ψ be defined by

ψ(v) = φ(v) if φ(v) ∈ {1, 2}, ψ(v) = φ(v) + 1 if φ(v) ∈ {3, 4}, and ψ(v) = φ(v) + 2 if φ(v) ∈ {5, 6}. One easily check that ψ is a 3-backbone 8-colouring of (G, F ).
2.2 q-backbone (q + 2)-colouring Theorem 17. Given a connected graph G and a spanning connected subgraph H, one can decide in polynomial time if BBC q (G, H) ≤ q + 2.

Proof. Observe first that if H is not bipartite, then BBC(H, H) ≥ 2q+1 by (1), and so BBC q (G, H) ≥ q + 3. So we first check if H is bipartite. If not, we return 'no'. If it is, we get a bipartition (A, B) of H.

Observe that if (G, H) has a q-backbone (q + 2)-colouring, then (free to rename A and B) all the vertices of A are coloured in {1, 2} and all the vertices of B in {q + 1, q + 2}, because H is connected. We then can transform our instance into an instance I(G, H) of 2SAT as follows. For each vertex v, we create a variable x v . Intuitively, for a vertex x ∈ A (resp. x ∈ B), the variable x v will be true if and only if v is coloured 1 (resp. q + 2) and false if and only if v is coloured 2 (resp. q + 1). Now for each edge uv, we create the following clauses.

• If u and v are both in A or both in B, we create the clauses x u ∨ x v and xu ∨ xv ;

• if u ∈ A and v ∈ B, we create the clause x u ∨ x v .
It is easy to check that (G, H) has a q-backbone (q + 2)-colouring if and only if I(G, H) is satisfiable.

Since 2SAT is well-known to be polynomial-time solvable, we can decide in polynomial time if BBC q (G, H) ≤ q + 2.

Theorem 18. For any q ≥ 2, the following problem is NP-complete. Input: A planar graph G and a 1-factor F of G. Question: BBC q (G, F ) ≤ q + 2?

Proof. The problem is trivially in NP since a q-backbone (q + 2)-colouring of (G, F ) is clearly a certificate.

Reduction from NOT-ALL-EQUAL 3SAT, which is defined as follows: Input: A set of clauses each having three literals. Question: Does there exists a suitable truth assignment, that is such that each clause has at least one true and at least one false literal?

This problem was shown NP-complete by Schaefer [START_REF] Schaefer | The complexity of satisfiability problems[END_REF].

Let C = {C 1 , . . . , C n } be a collection of clauses of size three over a set U of variables. We will construct a graph pair (G, F ) such that F is a 1-factor of G. Since V (F ) = V (G), we only precise which edges are in E(F ).

The following gadget will be useful. A forcing gadget at v or a forcing gadget with head v is the graph depicted in Figure 3. A key point in the reduction will be the following claim.

v 5 v v v 6 v 3 v 4 v 7 v 2 v 1
Claim 19. In any q-backbone (q + 2)-colouring of a forcing gadget, its head is coloured in {1, q + 2}.

Proof. Consider a forcing gadget, whose vertices are named as in Figure 3, and φ a q-backbone (q+2)colouring of it. Since all the vertices are matched in F , there all must be coloured in {1, 2, q+1, q+2}.

Assume for a contradiction that φ(v) = 2. Then φ(v 1 ) = q + 2. Thus φ(v 2 ) ∈ {1, q + 1}. Now if φ(v 2 ) = q + 1, then necessarily φ(v 3 ) = 1. Therefore, whatever the colouring may be, v 4 and v 5 are both adjacent to a vertex coloured 1. Hence {φ(v 4 ), φ(v 5 )} = {2, q + 2}. Therefore {φ(v 2 ), φ(v 3 )} = {1, q + 1}. But then v 6 cannot be coloured.

Similarly, we get a contradiction if φ(v) = q + 1.

For every variable u ∈ U , create a variable subgraph P u which is obtained from the path

(a 1 (u), b 1 (u), a 2 (u), b 2 (u), . . . , a n (u), b n (u)
) by adding a forcing gadget on each of its vertex.

For every clause C i = 1 ∨ 2 ∨ 3 , create a clause gadget D i as shown Figure 4. Then for each clause C i and each literal of C i , we add a path of length three (c i (l), c i (l), c i (l), a i (u)) if is the non-negated variable u, and (c i (l), c i (l), c i (l), b i (u)) if is the negated variable ū. We also add two forcing gadgets with heads c i (l) and c i (l).

c i ( 2 ) c i ( 1 ) d i ( 1 ) d i ( 3 ) c i ( 3 ) d i ( 2 )
It is easy to see that the resulting graph G may be drawn in the plane such that the crossed edges are those of type c i ( )c i ( ) for some literal . In particular, the two endvertices of a crossed edge are heads of forcing gadgets.

As long as there is a crossing C between two edges t(C)u(C) and v(C)w(C), we replace these two edges by the crossing gadget CG(C) depicted in Figure 5, so that the only edges that are possibly crossed (if there were several crossings on tu or uv) are t(C)t (C), u(C)u (C), v(C)v (C) and w(C)w (C). After this process, there is no more crossing so the resulting graph G is planar. Claim 20. Let φ be a q-backbone (q + 2)-colouring of (G, F ). For every crossing C in G , we have {φ(t(C)), φ(u(C))} = {1, q + 2} and {φ(v(C)), φ(w(C))} = {1, q + 2}.

u(C) t(C) v(C) w(C) u (C) d(C) a(C) c(C) b(C) v (C) w (C) t (C)
Subproof. By induction on the reverse order of creation of the crossing gadget. By construction, t(C), u(C), v(C), w(C), t (C), u (C), v (C), and w (C) are heads of forcing gadgets. So, by Claim 19, they are coloured 1 or q + 2. Without loss of generality, we may assume that φ(t(C)) = 1.

If the edge t(C)t (C) was crossed and then replaced by a series of crossing gadget, by induction, φ(t (C)) = q + 2. It is also trivially the case if t(C)t (C) still exists. Hence {φ(a(C)), φ(b(C))} = {1, q + 1}.

Assume for a contradiction that φ(u(C)) = q + 2. Then, as above, {φ(c(C)), φ(d(C))} = {1, q + 1}. This is a contradiction, because a(C)c(C) and a(C)d(C) are edges. Hence φ(u(C)) = q + 2, and so φ(u (C)) = 1 and {φ(c(C)), φ(d(C))} = {2, q + 2}.

In particular, one vertex of {a(C), b(C), c(C), d(C)} is coloured 1 and another is coloured q + 2. Now assume for a contradiction that {φ(v(C)), φ(w(C))} = {1, q+2}. Then v(C) and w(C) are both coloured 1 or both coloured q + 2, and so v (C) and w (C) are both coloured q + 2 or both coloured 1, respectively. This is a contradiction, as all vertices of {a(C), b(C), c(C), d(C)} are adjacent to some vertex in {v (C), w (C)}. ♦

Let us now prove that (G, F ) admits a q-backbone (q + 2)-colouring if and only if C has a suitable truth assignment.

Assume first that (G, F ) admits a q-backbone (q + 2)-colouring φ. Let u be a variable. Since there are heads of forcing gadgets, by Claim 19, all the a i (u) and b i (u) are coloured in {1, q + 2}. Moreover, since they form a path, all the a i (u) are coloured with the same colour and all the b i (u) are coloured with the other. Hence one can define the truth assignment ψ by ψ

(u) = true if φ(a i (u)) = 1 for 1 ≤ i ≤ n, and ψ(u) = f alse if φ(a i (u)) = q + 2 for 1 ≤ i ≤ n.
We shall prove that ψ is suitable.

Let C i = 1 ∨ 2 ∨ 3 be a clause. Claim 20 implies that for j ∈ {1, 2, 3}, φ(c i ( j )) = 1 if ψ( j ) = f alse and φ(c i ( j )) = q + 2 if ψ( j ) = true. Now the three c i ( j ), 1 ≤ j ≤ 3, cannot be all coloured 1 (resp. q +2), for otherwise {φ(d i ( 2 )), φ(d i ( 3 ))} must be {2, q +2} (resp. {1, q +1}) and so d i ( 1 ) cannot be coloured, because it must be coloured in {1, q + 2} as head of a forcing gadget. Thus at least one of the c i (l j ) is coloured 1 and at least one is coloured q + 2, and so C i has at least one true and at least one false literal.

Hence ψ is suitable.

Reciprocally, assume that C has a suitable truth assignment ψ. For all u ∈ U and all 1 ≤ i ≤ n, let us define φ(a i (u)) = 1 and φ(b i (u)) = q + 2 if ψ(u) = true, and φ(a i (u)) = q + 2 and φ(b i (u)) = 1 if ψ(u) = f alse. Similarly, for every literal , we set φ(c i ( )) = 1, φ(c i ( )) = q + 2, φ(c i ( )) = 1, if is false, and φ(c i ( )) = q + 2, φ(c i ( )) = 1, φ(c i ( )) = q + 2, if is true.

One can extend φ into a q-backbone (q + 2)-colouring of (G, F ). Indeed, it is sufficient to show that we can extend it to forcing, clause and crossing gadgets.

If v is the head of a forcing gadget and φ(v) = 1, we can set φ(v 1 ) = q + 2, φ(v 2 ) = q + 1, φ(v 3 ) = 1, φ(v 4 ) = q + 2, φ(v 5 ) = 2, φ(v 6 ) = 2, and φ(v 7 ) = q + 2. Similarly, we can extend the colouring to the forcing gadget if φ(v) = q + 2.

Consider a clause gadget D i . Since C i has at least one true and at least one false literal, at least one vertex of c i ( 1 ), c i ( 2 ) c i ( 3 ) is coloured 1 and at least one is coloured q + 2. If c i ( 1 ) is coloured q + 2, and c i ( 2 ) and c i ( 2 ) are assigned 1, then we can set φ(d i ( 1 )) = 1, φ(d i ( 2 )) = 2, and φ(d i ( 3 )) = q + 2. If c i ( 1 ) and c i ( 2 ) are coloured 1, and c i ( 3 ) is assigned q + 2, then we can set φ(d i ( 1 )) = q + 2, φ(d i ( 2 )) = q + 1, and φ(d i ( 3 )) = 1.

Finally consider a crossing gadget such that {φ(t(C)), φ(u(C))} = {φ(v(C)), φ(w(C))} = {1, q + 2}. By symmetry, we may assume that φ Proof. Reduction from PLANAR 3-COLOURABILITY, which consists of deciding if a given connected planar graph is 3-colourable. This problem was shown to be NP-complete by Stockmeyer [START_REF] Stockmeyer | Planar 3-colorability is polynomial complete[END_REF]. Clearly, it remains NP-complete when restricted to 2-connected planar graphs.

(t(C)) = φ(v(C)) = 1 and φ(u(C)) = φ(w(C)) = q + 2. Then we can set φ(t (C)) = φ(v (C)) = q + 2, φ(u (C)) = φ(w (C)) = 2, φ(a(C)) = 1, φ(b(C) = q + 1, φ(c(C)) = q + 2, and φ(d(C)) = 2.
Let H be a 2-connected planar graph. We shall construct a planar graph G and a galaxy F with maximum degree 3 in G such that BBC 2 (G, F ) ≤ 5 if and only if H is 3-colourable.

As a forcing gadget at v, we will use the parachute with harness v. It is easy to see that in a 2-backbone 5-colouring of a parachute, its harness is coloured in {1, 5}.

We consider any embedding of H. For each face (x 1 , x 2 , . . . , x k , x 1 ) of H, we put a cycle (z 1 , z 2 , . . . , z 2k , z 1 ), inside which we put parachutes on every vertex z i for every 1 ≤ i ≤ 2k. We then add the edges x i z 2i x i z 2i+1 for all 1 ≤ i ≤ k.

Assume that (G, F ) has a 2-backbone 5-colouring φ, then, because of the parachutes, all the vertices in the cycles added inside faces must be coloured in {1, 5}. Moreover consecutive vertices on one such cycles get different colours, so one is coloured 1 and the other is coloured 5. Hence all the vertices in H are coloured in {2, 3, 4}. Hence φ induces a proper 3-colouring on H with colours {2, 3, 4}.

Reciprocally, assume that H is 3-colourable. Then there exists a proper 3-colouring c of H into {2, 3, 4}. One can then colour all the cycles inside faces with 1 and 5. The colouring can then easily be extended into a 2-backbone 5-colouring of (G, F ).

Theorem 22. The following problem is NP-complete. Input: A planar graph G and a galaxy F in G with maximum degree 2. Question: Is BBC 2 (G, F ) ≤ 5?

Proof. The proof is identical to the one of Theorem 21. The only difference comes from the forcing gadget, which is more complicated because it cannot contains stars of degree 3 in F .

To construct the forcing gadget, we need an auxiliary gadget, called no-3-gadget. It is depicted in Figure 6.

Claim 23. In any 2-backbone 5-colouring of a no-3-gadget, its roof is not coloured in 3.

Proof. We will denote the vertices of the no-3-gadget by their names in Figure 6. Assume for a contradiction that there is a 2-backbone 5-colouring φ of a no-3-gadget such that φ(x) = 3. The forcing gadget is the one depicted in Figure 7.

Claim 24. In any 2-backbone 5-colouring of a forcing gadget, its head is coloured in {1, 5}.

Proof. Consider a forcing gadget, whose vertices are named as in Figure 7, and φ a 2-backbone 5colouring of it.

Let us prove that φ(w) = 3 and so that φ(v) ∈ {1, 5}. Assume for a contradiction that φ(w) = 3. Without loss of generality, we may assume that φ(w) ∈ {1, 2}.

Observe that the vertices x, y, z, x , y , z are not assigned 3 because they are roofs of no-3gadgets.

If φ(w) = 1, then (φ(x), φ(y), φ(z)) and (φ(x ), φ(y ), φ(z )) is either (4, 2, 5) or (5, 2, 4). Hence the vertices x, x and z are all coloured in {4, 5}, which is impossible, since they form a triangle.

If φ(w) = 2, then (φ(x), φ(y), φ(z)) and (φ(x ), φ(y ), φ(z )) is either (4, 1, 5) or (5, 1, 4). Hence the vertices x, x and z are all coloured in {4, 5}, which is impossible, since they form a triangle.

To get the equivalence between the 3-colourability of the original graph H and the existence of a 2-backbone 5-colouring of (G, F ), it remains to prove that for any α ∈ {1, 5}, there is a 2-backbone 5-colouring of the forcing gadget such that the head is coloured α.

We denote the vertices by their names in Figure 7. Set φ(w

) = 3, φ(x) = φ(y ) = 1, φ(y) = φ(z ) = 5, φ(z) = 2 and φ(x ) = 4.
Observe that no vertex in {x, y, z, x , y , z } has been coloured 3. Hence, it remains to prove that for any β ∈ {1, 2, 4, 5}, there is a 2-backbone 5-colouring of the forcing gadget such that the head is coloured β. By the symmetry φ → 6 -φ, it suffices to prove that one exists for β ∈ {1, 2}. We denote the vertices by their names in Figure 6. Let us denote by β the colour of {1, 2} \ {β}.

φ(a) = 3, φ(b) = β, φ(c) = 5, φ(d) = 4, φ(e) = β, φ(f ) = β, φ(a ) = 3, φ(b ) = 5, φ(c ) = β, φ(d ) = 5, φ(e ) = β, φ(f ) = 3, φ(g) = 1, φ(h) = 5, φ(i) = 3.

Hamiltonian-path backbone

Theorem 25. The following problem is NP-complete. Input: A planar graph G with a hamiltonian path P . Question: BBC 2 (G, P ) ≤ 5?

To prove this theorem, we shall use a reduction similar to the one of Theorem 21. However, we do not reduce directly from PLANAR 3-COLOURABILITY but use an intermediate problem whose NP-completeness is proven by reducing PLANAR 3-COLOURABILITY to it.

This intermediate problem is the following: TRACEABLE PLANAR 3-COLOURABILITY Input: A planar graph G with a hamiltonian path P . Question: Is G 3-colourable? Lemma 26. TRACEABLE PLANAR 3-COLOURABILITY is NP-complete.

Proof. Reduction from PLANAR 3-COLOURABILITY. Let H be a connected planar graph. We will construct a planar graph G having a hamiltonian path P such that χ(G) ≤ 3 if and only if χ(H) ≤ 3.

To do so, we shall construct a sequence of pairs

(G i , P i ) for 1 ≤ i ≤ |V (H)| such that P i is a path in the planar connected graph G i , |V (P i )| = |V (G i )| -|V (H)| + i, and χ(G i ) ≤ 3 if and only if χ(H) ≤ 3.
Then the path P := P V (H) will be a hamiltonian path of G := G V (H) and χ(G) ≤ 3 if and only if χ(H) ≤ 3.

Let x be a vertex of H. We set G 1 := H and P 1 := (x). Trivially, (G 1 , P 1 ) verifies the above property.

Assume now that i ≥ 1 and let us construct (G i+1 , P i+1 ) from (G i , P i ). Let P i = (v 1 , v 2 , . . . , v ) be a path. Since G i is connected, there exists j such that v j is adjacent to a vertex y in V (G i ) \ V (P i ). If j = 1, then let P i+1 := (y, v 1 , v 2 , . . . , v ), and G i+1 := G i ; if j = p, then let P i+1 := (v 1 , v 2 , . . . , v , y), and G i+1 := G i ; if y is also incident to v j+1 , let P i+1 := (v 1 , . . . , v j , y, v j+1 , . . . , v )). In those three cases, (G i+1 , P i+1 ) has trivially the desired property.

So we may assume that 1 < j < and y is not adjacent to v j+1 . Let y 1 , y 2 , . . . y r be the neighbours of v j in their order around it such that v j+1 = y r , y k = y and v j-1 = y q for q < r.

Let G i+1 be the graph obtained from G i as follows. For all 1 ≤ s ≤ k -1, remove the edge v j y s , add three vertices a s , b s , c s and the edges a s b s , b s c s , c s a s , v j a s , v j b s , b s y s ; Add the edges c s a s+1 for all 1 ≤ s ≤ k -2, and v j+1 a 1 . Finally add a vertex y and the edges yy and y c k-1 . Let P i+1 be the path obtained from P i by replacing the edge v j v j+1 by the subpath

(v j , y, c k-1 , b k-1 , a k-1 , . . . , c 1 , b 1 , a 1 , v j+1 ).
See Figure 8, which illustrates the construction when k = 5. Clearly, the number of vertices not covered by P i+1 in G i+1 is one less than the number of vertices not covered by

P i in G i . So, since |V (P i )| = |V (G i )|-|V (H)|+i, we have |V (P i+1 )| = |V (G i+1 )|- |V (H)| + i + 1.
It remains to prove that G i+1 is 3-colourable if and only if G i is. Assume first that G i+1 admits a proper 3-colouring φ in {1, 2, 3}. We claim that it also induces a proper 3-colouring of G i . Indeed, without loss of generality, we may assume that φ(v j ) = 1 and φ(v j+1 ) = 2. Then for all 1 ≤ s ≤ k -1, φ(a s ) = 3 and φ(c s ) = 2, so φ(b s ) = 1. Hence φ(y s ) = 1. Therefore, for all 1 ≤ s ≤ k -1, φ(y s ) = φ(v j ). Since the v j y s , 1 ≤ s ≤ k -1, are the only edges of G i which are not in G i+1 , φ is a proper 3-colouring of G i .

Conversely, assume that G i admits a 3-colouring φ in {1, 2, 3}. It induces a partial proper 3colouring of G, such that φ(v j ) = φ(y s ) for all 1 ≤ s ≤ k -1. Let us extend it. Without loss of generality, φ(v j ) = 1 and φ(v j+1 ) = 2. For all 1 ≤ s ≤ k -1, set φ(a s ) = 3, φ(b s ) = 1, and φ(c s ) = 2. Finally, colour y with the colour in {1, 2, 3} \ {φ(y), φ(c k-1 )}. This gives a proper 3-colouring of G i+1 .

Proof of Theorem 25. Reduction from TRACEABLE PLANAR 3-COLOURABILITY. Let (H, Q) be an instance of this problem. We shall construct a graph G and a hamiltonian path P of G such that BBC 2 (G, P ) ≤ 5 if and only if χ(H) ≤ 3. To do so we start from H and for each edge xy of Q, we will plug in an edge gadget E(xy) containing a hamiltonian path P (xy) from x to y. The union of all the P (xy), xy ∈ E(Q), will then be a hamiltonian path P of the resulting graph G.

To construct the edge gadget, we use an auxiliary forcing gadget depicted in Figure 9. The head of such a gadget is the vertex denoted by v in the figure. Its fringes are the vertices denoted by a and e. Proof. We denote the vertices by their names in Figure 9. Suppose for a contradiction that there is a 2-backbone 5-colouring φ such that φ(v) / ∈ {2, 4}. By the symmetry φ → 6 -φ, we may assume that φ(v) ∈ {1, 3}.

If Assume first that (G, P ) admits a 2-backbone 5-colouring φ. Since H is a subgraph of G, φ induces a proper colouring on H. We shall prove that every vertex of H is coloured in {1, 3, 5}, thus proving that this proper colouring uses (at most) 3 colours.

Every vertex v of H is contained in an edge xy of Q, so it is contained in the edge gadget E(xy) in G. So it is adjacent to two vertices (namely v 1 and v 2 if v = x, and v 2 and v 3 if v = y), which are heads of forcing gadgets and adjacent. Hence by Claim 27, one of these vertices is coloured 2 and the other is coloured 4. Hence v must be coloured in {1, 3, 5}. Let us now assume that H is 3-colourable. Then there exists a proper colouring φ of H with {1, 3, 5}. Let us now extend into a 2-backbone 5-colouring of (G, P ). It is sufficient to prove that we can extend it to every edge-gadget.

To extend it to the edge-gadget E(xy) (we use the names of Figure 10), set φ(v 1 ) = φ(v 3 ) = 2 and φ(v 2 ) = 4. Now, since for any pair (α, β) ∈ {1, 2, 3, 4, 5} 2 , there is a 2-backbone 5-colouring of the path of length 4 such that the first vertex is coloured α and the last vertex is coloured β, it suffices to prove that we can extend φ to the forcing gadget.

Consider such a forcing gadget (with vertex names as in Figure 9). Then φ(v) ∈ {2, 4}. By the symmetry φ → 6 -φ, we may assume that φ(v) = 2. Then setting φ(a) = 4, φ(b) = φ(d) = 1, φ(c) = 3 and φ(e) = 5, we obtain the desired extension.

Hence, BBC 2 (G, P ) ≤ 5.

2.4 q-backbone (q + 3)-colouring for q ≥ 3 Theorem 28. For any q ≥ 3, the following problem is NP-complete. Input: A planar graph G and a galaxy F in G with maximum degree 3. Question: Is BBC q (G, F ) ≤ q + 3?

Proof. Reduction from PLANAR 3-COLOURABILITY.

We shall need the graph, which we call a kite, depicted in Figure 11. The vertex named t in the figure is the tip of the kite, and the one named u is its corner.

Claim 29. If φ is a q-backbone (q +3)-colouring of a kite such that φ(t) ∈ {1, 2, 3, q +1, q +2, q +3}, then either φ(t) ∈ {1, 2, 3} and φ(u) = q + 3, or φ(t) ∈ {q + 1, q + 2, q + 3} and φ(u) = 1.

Proof. Observe that the vertices v, z 1 , z 2 , z 3 are harnesses of parachutes. Thus, by Proposition 14-(i), they must be assigned 1 or q + 3.

Assume that φ(v) = 1, then φ(z 1 ) = φ(z 2 ) = φ(z 3 ) = q+3. Thus {φ(s 1 ), φ(s 2 )} = {q+1, q+2} and so φ(u) = q + 3 and φ(t) ∈ {1, 2, 3}.

Similarly if φ(v) = q + 3, we obtain φ(u) = 1 and φ(t) ∈ {q + 1, q + 2, q + 3}.

Let H be a planar graph. Let (G, F ) be the graph pair obtained from H as follows. Firstly, for each face f of H, we create a parachute P f with harness v f , and for each vertex x incident to f , we

s 2 z 3 t z 1 s 1 v u z 2
Figure 11: The kite create a kite K f (x) with tip x and corner u f (x). We then link the vertex v f to all the u f (x). Secondly, for every vertex x ∈ V (H), we add a vertex y x and the edge xy x in the backbone.

Clearly, the resulting graph G is planar and the resulting backbone F is a galaxy with maximum degree 3.

Let us now prove that BBC q (G, F ) ≤ q + 3 if and only if H is 3-colourable. Assume first that (G, F ) admits a q-backbone (q + 3)-colouring φ. Observe that each vertex x in V (H) is coloured in {1, 2, 3, q + 1, q + 2, q + 3}, because it is adjacent to y x in F .

Let x be a vertex in V (H). Free to consider q + 4 -φ, we may assume that φ(x) ∈ {1, 2, 3}. Consider a face f incident to x in H. By Claim 29, the kite K f (x) has its corner coloured q + 3. Together with Proposition 14-(i), this implies that φ(v f ) = 1. Thus, the corner of the kites in f cannot be coloured 1, therefore there are coloured q + 3 and so by Claim 29, all the vertices incident to f in H are all coloured in {1, 2, 3}. Applying this reasoning to each face of H, we obtain that all vertices of H are coloured in {1, 2, 3}. Hence, φ induces a proper 3-colouring on H.

Conversely, assume that H admits a proper 3-colouring c. One can extend it into a q-backbone (q + 3)-colouring of (G, F ) as follows. For every x ∈ V (H), we colour y x with q + 3; for every face f , we colour the vertex v f with 1 and the corners of the kites by q + 3. One can then extend the colouring to each kite (as in the proof of Claim 29) to obtain a q-backbone (q + 3)-colouring of (G, F ).

The reduction above can be modified to have a spanning tree T for the backbone in place of the galaxy F . It suffices consider a spanning tree U of H and do the following: add a path of length two in the backbone along each edge of the tree U ; for each kite, add tz 3 and vz 3 in the backbone and add paths of length two in the backbone along edges z 1 v and z 2 v. This will prove the following statement.

Theorem 30. The following problem is NP-complete. Input: A planar graph G and a spanning tree T of G.

Further research

Campos et al. [START_REF] Campos | Backbone colouring: tree backbones with small diameter in planar graphs[END_REF] proved that if G is planar and T has diameter at most 3, then BBC 2 (G, T ) ≤ 5. Hence one can the find the 2-backbone chromatic number of such a pair in polynomial time. One can ask of the complexity for larger diameter. If G is a triangle-free planar graph, then, by Grötzsch's Theorem [START_REF] Grötzsch | Ein dreifarbensatz fr dreikreisfreie netze auf der kugel[END_REF], it is 3-colourable, and so BBC q (G, H) ≤ 2q + 1 and CBC q (G, H) ≤ 3q for any subgraph H of G. Hence Conjecture 1 and Conjecture 6 for q = 2, hold when G is triangle-free. A natural next step would be to prove Conjecture 6 for values of q larger than 2 when G is triangle-free.

Steinberg's Conjecture (1976) states that every planar graph without 4-and 5-cycles is 3-colourable. Towards this, Erdős (1991) proposed the following relaxation of Steinberg's Conjecture: Determine the smallest value of k, such that every planar graph without cycles of length from 4 to k is 3colourable. The best known bound for such a k is 7 which was proved by Borodin, Glebov, Raspaud and Salavatipour [START_REF] Borodin | Planar graphs without cycles of length from 4 to 7 are 3-colorable[END_REF]. Hence, an evidence to both Conjecture 6 and Steinberg's Conjecture would be to prove the following: Conjecture 44. If G is a planar graph without 4-and 5-cycles and F a spanning forest of G, then CBC 2 (G, F ) ≤ 7.

Conjecture 3 .

 3 If G is a planar graph and F a forest in G, then BBC 3 (G, F ) ≤ 8. If true, Conjecture 3 would be tight. The pair (G * , F * ) of Figure 2 satisfies BBC 3 (G * , F * ) = 8. We show in Proposition 16 that Conjecture 1 implies Conjecture 3.

Figure 3 :

 3 Figure 3: A forcing gadget with head v (left) and its symbol (right) (Edges of E(F ) are in bold.)

Figure 4 :

 4 Figure 4: The clause D i . (Edges of E(F ) are in bold, forcing gadgets are represented by their symbols.)

Figure 5 :

 5 Figure 5: The crossing gadget CG(C). (Edges of E(F ) are in bold, forcing gadgets are represented by their symbols.)

  The following problem is NP-complete. Input: A planar graph G and a galaxy F in G with maximum degree 3. Question: Is BBC 2 (G, F ) ≤ 5?

  Assume first that φ(a) ∈ {4, 5}, then φ(b) ∈ {1, 2} and {φ(a), φ(c)} = {4, 5}. Hence φ(d) ∈ {1, 2} and so {φ(f ), φ(c)} = {4, 5}. Therefore φ(e) = 3 and so φ(d) = 1. Similarly, if φ(a) ∈ {1, 2}, we obtain that φ(d) = 5. Hence, φ(d) ∈ {1, 5}. Similarly, φ(d ) ∈ {1, 5}. Free to consider 6 -φ instead of φ, we may assume that φ(d) = 1 and φ(d ) = 5. Thus φ(f ) = 2. Now φ(g) ∈ {3, 4}. If φ(g) = 3, then {φ(i), φ(h)} = {1, 5}, and if φ(g) = 4, then {φ(i), φ(h)} = {1, 2}. In both cases, one of h and i is coloured 1, which is impossible because φ(d) = 1.

Figure 6 :

 6 Figure 6: The no-3-gadget with roof x and its symbol.

Figure 7 :

 7 Figure 7: The forcing gadget with head v. (Edges of E(F ) are in bold, no-3-gadgets are represented by their symbols.)

Figure 8 :

 8 Figure 8: Constructing (G i+1 , P i+1 ) from (G i , P i ) (Egdes of the paths are in bold.)

Figure 9 :

 9 Figure 9: The forcing gadget with head v and fringes a and e (left) and its symbol (right)

  φ(v) = 3, then all the vertices a, b, c, d, e are coloured in {1, 2, 4, 5}. On the path (a, b, c, d, e), vertices coloured {1, 2} alternate with vertices coloured {4, 5}. Hence a, c, and e are all coloured in {1, 2}, or all coloured in {4, 5}, which is a contradiction as they form a clique. If φ(v) = 1, then all the vertices a, b, c, d, e are coloured in {2, 3, 4, 5}. Now φ(b) is at distance 2 from the two distinct colours φ(a) and φ(c), hence φ(b) ∈ {2, 5}. Similarly, φ(d) ∈ {2, 5}. But φ(c) is at distance 2 from φ(b) and φ(d), so φ(b) = φ(d). Then the three vertices a, c, and e are all coloured in {2, 3, 4, 5} \ {φ(b) -1, φ(b), φ(b) + 1}, which has cardinality 2. This is a contradiction as those three vertices form a clique. Now the edge gadget is the one depicted in Figure 10.Let us now prove that BBC 2 (G, P ) ≤ 5 if and only if χ(H) ≤ 3.

3 Figure 10 :

 310 Figure 10: The edge gadget E(xy) and its hamiltonian path P (xy) in bold (Forcing gadgets are represented by their symbols.)

Problem 43 .

 43 For a fixed d ≥ 4, what is the complexity of finding the 2-backbone chromatic number of (G, T ), when G is planar and T a spanning tree of diameter d ? Since, for any fixed k ≤ 4, deciding if the 2-backbone chromatic number of (G, T ) is at most k can be done in polynomial time, if Conjecture 1 holds, Problem 43 is equivalent to finding the complexity of deciding if BBC 2 (G, T ) ≤ 5.

Question: Is BBC q (G, T ) ≤ q + 3? 2.5 q-backbone (q + 5)-colouring Theorem 31. For any q ≥ 4, the following problem is NP-complete. Input: A planar graph G and a spanning tree T of G. Question: Is BBC q (G, T ) ≤ q + 5?

Proof. Reduction from PLANAR 3-COLOURABILITY.

Let H be a planar graph. We shall construct a planar graph G together with a spanning tree T such that H is 3-colourable if and only if BBC q (G, T ) ≤ q + 5. Take U be a spanning tree of H.

We first construct a graph G from H by adding for every edge e = uv of U a vertex x e linked to u and v. We let T be the spanning tree of G induced by the new edges. The pair (G, T ) is then obtained from (G , T ) by adding a parachute on every vertex. Clearly G is planar as for each edge e = uv the path ux e v can be drawn along the edge uv.

Suppose that (G, T ) admits a q-backbone (q + 5)-colouring. Then by Proposition 14-(iii), every vertex in G is coloured in {1, 2, 3, q + 3, q + 4, q + 5}. Note that the vertices of H form one of the part of the bipartition of T . Hence, the colours of the vertices of H are either all in {1, 2, 3} or all in {q + 3, q + 3, q + 5}. In both cases, φ induces a proper 3-colouring on H.

Conversely, it is straightforward to extend a a proper 3-colouring of H into a q-backbone (q + 5)colouring of (G, T ).

Circular backbone colouring

The following Proposition is an analogue to Proposition 13 and its proof is similar.

Proposition 32. Let G be a graph and let H be a subgraph of G such that 2 ≤ χ(H) < χ(G). Then CBC q (G, H) ≤ (χ(G) + q -2)χ(H).

Proof. Let g be a proper χ(G)-colouring of G and h a proper χ(H)-colouring of H.

Assume first that χ(H) is even. Let f be the colouring defined by:

. These intervals do not intersect and two consecutives intervals are separated by q -2 elements. In particular, if

Consider an edge uv ∈ E(G). By the previous remark, if

Consider now an edge uv ∈ E(H). Then h(u) = h(v), so f (u) and f (v) are in different I i . If they are in non-consecutive

Assume now that χ(H) is odd. Let f be the colouring defined by:

Similarly to the even case, one can check that f is a circular q-backbone ((χ(G) + q -2)χ(H))colouring of (G, H).

Planar graphs of girth at least 5

Theorem 33. Let G be a planar graph of girth at least 5 and M a matching in G.

Proof. Our proof is based on a structural result of Borodin and Glebov [START_REF] Borodin | On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph[END_REF]. See also [START_REF] Kawarabayashi | Decomposing a planar graph of girth 5 into an independent set and a forest[END_REF].

Theorem 34 (Borodin and Glebov [START_REF] Borodin | On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph[END_REF]). The vertex set of every planar graph of girth at least 5 can be partitioned into an independent set and a set which induces a forest.

Let (S, F ) be a partition of V (G) such that S is stable and F induces a forest. Let us colour every vertex of S with 1. Now since F is a forest, it has an ordering v 1 , . . . , v p such that for every i, v i has at most one neighbour in {v 1 , . . . , v i-1 }. We colour the vertices of F according to this ordering as follows. If v i has no neighbour in {v 1 , . . . , v i-1 }, then colour it with q + 1. If v i has a neighbour u in {v 1 , . . . , v i-1 } and uv i / ∈ E(M ), then colour it with a colour of {q + 1, q + 2} not assigned to u. If v i has a neighbour u in {v 1 , . . . , v i-1 } and uv i ∈ E(M ), then assign 2q + 1 (resp. 2 to v i ) if u is coloured q + 1 (resp. q + 2). It is easy to check that the obtained colouring is a q-backbone Z 2q+1 -colouring of (G, M ).

Circular q-backbone 2q-colouring

Proposition 35. Let G be a graph and H a spanning connected subgraph of G.

Assume now that (G, H) admits a circular q-backbone 2q-colouring f . Let v be a vertex of G. Without loss of generality, we may assume that f (v) = 1. Then all the neighbours of v in H must be coloured q + 1. And so on, by induction, all the vertices at even distance from v in H are coloured 1 and all the vertices at odd distance from v in H are coloured q + 1. Since H is connected and spans G, it follows that all vertices are coloured 1 or q + 1, so G is bipartite.

Proposition 35 implies that given a graph G and a spanning connected subgraph H, deciding if CBC q (G, H) = 2q can be done in polynomial time. In contrast, if the condition of G be connected is removed, when q = 2, the problem becomes NP-complete, as shown by the following theorem.

Theorem 36. The following problem is NP-complete. Input: A planar graph G and a matching M in G.

Proof. The problem is trivially in NP since a circular 2-backbone 4-colouring of (G, F ) is clearly a certificate.

To prove it is NP-complete, we give a reduction from NOT-ALL-EQUAL 3SAT.

Let C = {C 1 , . . . , C n } be a collection of clauses of size three over a set U of variables. We will construct a graph pair (G, M ) such that M is a matching in G.

To do so we need some definitions and gadgets. Colours 1 and 3 are said to be twins and so do the colours 2 and 4. Trivially two vertices joined by an edge of M receives distinct twin colours. Two colours are siblings if they are equal or twins.

A link with ends u and v and central edge w 1 w 2 is a subgraph with vertex set {u, v, w 1 , w 2 } and edge set {uw 1 , uw 2 , vw 1 , vw 2 , w 1 w 2 } with w 1 w 2 ∈ M . Two ends of a link are said to be linked.

Claim 37. In a circular 2-backbone 4-colouring c, the colours of the ends of a link are siblings.

Proof. The two vertices w 1 and w 2 are joined by an edge of M , so {c(w 1 ), c(w 2 )} ∈ {{1, 3}; {2, 4}}. Hence if u is coloured in {1, 3} (resp. {2, 4}), then {c(w 1 ), c(w 2 )} is {2, 4} (resp. {1, 3}), and so v is coloured in {1, 3} (resp. {2, 4}).

For each variable u ∈ U , we create a variable gadget G u which is obtained from the distinct vertices a u 1 , a u 2 , . . . , a u n by linking, from 1 ≤ i ≤ n -1, the vertices a u i and a u i+1 by an link with central edge b u i c u i . Claim 37 (and its proof) immediately implies the following.

Claim 38. In a circular 2-backbone 4-colouring of G u , all the a i u are coloured with two sibling colours and all the b i u with the two other colours (which are also siblings). For each clause C i = i 1 ∨ i 2 ∨ i 3 , we create a triangle z i 1 z i 2 z i 3 . Now for j = 1, 2, 3, if i j is the nonnegated literal u, we join z i j with a u i , and if i j is the negated literal ū, we join z i j with b u i . Such edges are said to be red. So far, the obtained graph H is not planar, but we can clearly draw it such that only red edges cross. We can now subdivide every red edge into a red path such that every edge is crossed at most once. We then replace the red edges which are not crossed by a link (with the same end) and two red edges uv and xy that cross each other by the crossing gadget depicted in Figure 12. The resulting graph G is planar and it comes with a matching M . Proof. Consider first a circular 2-backbone 4-colouring of the crossing gadget. u is linked to u , which is linked to v , which in turn is linked to v. Hence, by Claim 37, the colours of u and v are siblings. Assume that x is coloured in {1, 3}, then x is also coloured in {1, 3}, say 1. The vertices a and b are assigned twin colours, so one is coloured 2 and the other 4. We now distinguish two cases depending on the colour of u .

1. Assume u is coloured 3. Then v must also be coloured 3. The vertices c and d are assigned twin colours, so one is coloured 2 and the other 4. Hence y is coloured 1.

2. Assume u is coloured in {2, 4}. Without loss of generality, we may assume it is coloured 2.

Then a is coloured 4 and b is coloured 2, so v is coloured 4. Hence y is coloured in {1, 3}.

In both cases the colour of x and y are siblings, and so, by Claim 37, the colours of x and y are siblings.

For any 4-tuple {c u , c v , c x , c y } such that c u and c v are siblings and c x and c y are siblings, finding the desired circular 2-backbone 4-colouring is straightforward and left to the reader.

We shall now prove that C admits a suitable truth assignment if and only if CBC 2 (G, M ) ≤ 4.

Assume first that (G, M ) admits a circular 2-backbone 4-colouring. Let φ be the truth assignment defined by φ(u) = true if all the a i u are coloured in {1, 3}, and φ(u) = f alse if all the a i u are coloured in {2, 4}. Note that is well defined by Claim 38. Now by Claims 37 and 39, for each clause

, the vertex z i j is coloured in {1, 3} if and only if the literal i j is true. But since z i 1 z i 2 z i 3 is a triangle, at least three colours must appear on these vertices, and so at least one from {1, 3} and at least one from {2, 4}. Hence, at least one of the literals of C i is true and at least one is false. Thus φ is suitable. Reciprocally, assume that C admits a suitable truth assignment φ. If φ(u) = true, then colour all the a i u with 1, all the b i u with 2 and all the c i u with 4. And if φ(u) = f alse, then colour all the a i u with 2, all the b i u with 1 and all the c i u with 3. Now, for each clause

1 , is true and some literal, say i 3 , is false. Then assign 1 to z i 1 , 2 to z i 3 , and colour z i 2 with 3 if i 2 is true and 4 otherwise. By Claims 37 and 39, this partial colouring may be extended into a circular 2-backbone 4-colouring of (G, M ).

Theorem 40. The following problem is NP-complete. Input: A planar graph G and a matching M in G. Question: Is CBC 2 (G, M ) ≤ 5?

Proof. The reduction is from PLANAR C 5 -COLOURING which is defined as follows: Input: A planar graph G.

Question: Does G have a homomorphism onto C 5 , the cycle of length 5?

This was proved to be NP-complete by MacGillivray and Siggers [START_REF] Macgillivray | On the complexity of H-colouring planar graphs[END_REF].

To make the reduction we need an edge gadget. This gadget is built from the planar graph H 1 (u, v) together with the matching M 1 (u, v) depicted in Figure 13.

w u v

Figure 13:

The graph H 2 (u, v) is obtained from H 1 (u, v) by replacing the edge uw by H 1 (w, u). The matching M 2 (u, v) is then the union of M 1 (u, v) \ {uw} and M 1 (w, u). Observe that u and v are incident to no edges of M 2 (u, v). The pair (H 2 (u, v), M 2 (u, v)) is the edge gadget.

Broersma et al. [START_REF] Broersma | λ-backbone colorings along pairwise disjoint stars and matchings[END_REF] proved that in any circular 2-backbone 5-colouring of (H 1 (u, v), M 1 (u, v)), vertices u and v receive colours which are cyclically 2 apart. In addition, it is straightforward to see that any precolouring of u and v with colours that are cyclically 2 apart can be extended into a circular 2-backbone 5-colouring of (H 1 (u, v), M 1 (u, v)). These two facts imply the following claim.

Claim 41.

(i) In any circular 2-backbone 5-colouring of (H 2 (u, v), M 2 (u, v)), vertices u and v receive colours which are cyclically 2 apart.

(ii) Any precolouring of u and v with colours that are cyclically 2 apart can be extended into a circular 2-backbone 5-colouring of (H 2 (u, v), M 2 (u, v)).

Let H be an instance of PLANAR C 5 -COLOURING. Replace each edge uv ∈ E(G) by an edge gadget (H 2 (u, v), M 2 (u, v)) to obtain a planar graph G and a matching M (the union of the M 2 (u, v)). By Claim 41-(i), every circular 2-backbone 5-colouring of (G, M ) induces a C 5 -colouring of H (the vertices of the C 5 are the colours (1, 3, 5, 2, 4)). Conversely, by Claim 41-(ii), any C 5 -colouring of H can be extended into a circular 2-backbone 5-colouring of (G, M ). Hence H admits a C 5 -colouring if and only if (G, M ) admits a circular 2-backbone 5-colouring.

Adding long paths along existing edges to transform the matching into a spanning tree, one derives the following: Theorem 42. The following problem is NP-complete. Input: A planar graph G and a spanning tree T of G. Question: Is CBC 2 (G, T ) ≤ 5?