Hajos Calculus on Planar Graphs (Theoretical Computer Science and its Applications)

13

Haj\’os

Calculus

on

Planar Graphs

京都大学大学院情報学研究科 花谷 陽一 (YoichiHanatani)

堀山 貴史 (TakashiHoriyama)

岩間 一雄 (Kazuo Iwama)

Graduate SchoolofInformatics,Kyoto University

Abstract: TheHajoscalculus isanondeterministic procedure whichgeneratestheclassof

non-3-colorablegraphs [3]. Ifallnon-3-co1orab1e graphscan be constructedin polynomial steps by the

calculus, NP$=$ co-NPholds.

UP

todate, however,it remains openwhether thereexists afamily

of graphs that can be generatedin polynomial steps. To attackthis problem, we proposetwo

graphcalculi $VHC$ and$P\mathcal{H}C^{*}$ that generate non-3-co1orab1eplanar graphs,whereintermediate

graphs inthe calculi arealso restricted to be planar. Then

we

prove that $P’HC$ and$PHC^{*}$ are

sound and complete. We also showthat$PHC^{*}$

can

polynomialiysimulate$PHC$

.

Keywords: Hajos calculus, Planar graph, Coloring, Proofsystems

1

Introduction

Graph$k$-coloring problem isthe problemto decide whetherwe can assignoneof$k$ colorstoeachvertexso

that adjacentpairsof verticesareassigneddifferent colors [15]. This problemisoneof themostfundamental

$\mathrm{N}\mathrm{P}$-complete problems $[5, 9]$. Even when $k\geq 3$, it is

$\mathrm{N}\mathrm{P}$complete. When $k\leq 2$, we

can

solve the problem

in polynomial time. If graphs are restricted to be planar, it is believed for along time that every graph

is 4-colorable [10]. Appel and Haken finally proved the Four-Color Theorem, i.e., every planar graph is

4-colorable $[7_{7}8,12, 19]$

.

Therefore, when $k\geq 4$, we can decide whether given planar graph is $karrow \mathrm{c}\mathrm{o}\mathrm{l}\mathrm{o}\mathrm{r}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}$

inpolynomialtime. When $k=3$, the problem is still NP-complete.

In order to characterize $k$-colorable graphs, many approaches have been attempted. The most typical

oneisHadwiger’sconjecturetorelatethenon-&-colorabilityand the$(k+1)$-cliques [1]. Let $k$be the fewest

numberofcolors necessary to color verticesinagivengraph. Then,wecan obtaina$k$-cliqueby contracting

adjacentvertices. This conjecture istrue for $k$_{$\leq 5[1,2, 4]$}.

Anotherapproachis theHajoscalculus. The calculusisanondeterministicprocedurethatconstructsall

non-fc-colorablegraphsfrom a $(k+1)$-clique [3]. A graph calculus is acollection of initial graphs, together

with

a

finite set of rules which allowsustoderivenew graphs. Aconstruction ofagraph$G$isasequence of

graphs $(G_{1}, G_{2}, \ldots, G_{l})$ such that the sequence ends with $G$ (i.e., _{$G_{t}=G$}) and every graphinthe sequence

is

one

of the initial graphs, orfollows from itsprevious graphsby applying oneofthe rules.

The complexity oftheHaj\’os calculuswasfirst studiedbyMansfield andWelsh [11]: If allnon-3-co1orab1e

graphshavepolynomial sizeHajos constructionsthen, NP$=$ co-NPholds,thus there mayexistgraphs that

cannot beconstructed in polynomialsteps. A construction of

a

graph in theHajos calculusgivesthe proof

of the non-k-colorability of the graph.

Our Contribution: Our motivation is to give intermediate subsystemsthat

are

more powerful than

bounded-depth Frege system and yet we

can

prove super-polynomial lower bounds. For this purpose,

we

considerthecalculus onplanar graphs,

more

precisely, thecalculusthat generates theclassofnon-3-co1orab1e

planar graphs, where intermediate graphs in the calculus are also restricted to be planar. Although the

Haj\’oscalculus

can

generate all$\mathrm{n}\mathrm{o}\mathrm{n}rightarrow 3$-colorableplanar graphs, intermediate graphs

are

not guaranteed to

be planar. When restrictingthe intermediate graphs to be planar, by adding only one

new

rule, we can

obtain a sound and complete calculus $PHC$. By modifying thesecond rule (edgeelimination rule) in the

Haj\’oscalculus, we

can

obtain another sound and complete calculusP7{C*. Wecomparethe powers of the

two calculi.

Previous work: It is knownthat the Hajoscalculusis polynomialiy bounded if and only ifExtended

Fregeproofsystems arepolynomialiybounded [16]. This result links an open problem ingraph theory to

an

important open problem in thecomplexity ofpropositional proof systems: Is therea strong system to

bounds on the subsystemsofthe Haj\’os calculus $[16, 17]$.

2

Haj\’os

Calculus

We describe the Haj\’os calculus for $k=3$. The set ofinitial graphs inHaj\’os calculus contains all graphs

isomorphictocomplete graph$K_{4}$. There

are

three rules for generatingnewgraphs:

1. $\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{x}/\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}$ introduction rule: Add (any numberof) vertices and edges,

2. Join rule: Let$G_{1}$ and$G_{2}$ be disjoint graphs,$a_{\mathrm{I}}$ and$b_{1}$ adjacent verticesin

$G_{1}$, anda2and$b_{2}$ adjacent

vertices in$G_{2}$. Constrcta graph$G_{3}$ from$G_{1}\cup G_{2}$ asfollows. First,

remove

edges (al, bl) and (a2,$b_{2}$) ;

then add

an

edge $(b_{1}, b_{2})$; lastly, contractvertices$a_{1}$ and a2 intoasingle vertex, named $a_{1}$.

3. Contraction rule: Contract two nonadjacent vertices intoasinglevertex, and

remove

any resulting

duplicated edges,

$\mathrm{V}\mathrm{e}\mathrm{r}\mathrm{t}\mathrm{e}\mathrm{x}/\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}$introductionruleimplies that ifasubgraphof$G$hasaconstruction, $G$also has aconstruction.

Rules 1 and 2 increase vertices$\mathrm{a}\mathrm{n}\mathrm{d}/\mathrm{o}\mathrm{r}$ edges,but Rule 3reduces vertices and edges, thus theconstruction

maynot be polynomially bounded.

We consider a minor revision of the Hajos calculus, $?tC$

.

The system HC has the same set ofinitial

graphs, aswell as Rules 1 and 3 of the Hajos calculus, but now Rule 2 of the Hajos calculusisreplaced by

the following rule:

2. Edge elimination rule: Let $G_{1}$ and $G_{2}$ be two graphs with

common

vertexset $\{v_{1},$

\ldots ,$v_{n}\}$which

are identicalexceptthat $G_{1}$ contains edges $(v_{1}, v_{2})$ and $(v_{2}, v_{3})$ and not $(v_{1}, v_{3})$, whereas$G_{2}$ contains

edges $(v_{1}, v_{2})$ and $(v_{1}, v_{3})$ and not $(v_{2}, v_{3})$. Then from$G_{1}$ and$G_{2}$,we

can

construct a graph$G_{3}$ that

is identical to $G_{1}$ but does not contain $(v_{2}, v_{3})$.

To associate twocalculi, Haj\’os calculus and$\mathcal{H}C$,wedefineabinaryrelation: Let$C$ and$C’$ be two graph

calculus systems, then$Cp$-simulates $C’$ if thereis a polynom ial-tim $\mathrm{e}$computable function $f$

so

that for all

graphs$G$, if$s$ isagraph construction of$G$in$C’$, then $f(s)$ isagraphconstructionof$G$ in C. $C$ and$C’$

are

$p$-equivalent if$C$psimulates $C’$and $C’p$-simulates $C$.

Fact 1 $\mathcal{H}C$ is

$p$-equivalent tothe Haj\’os calculus.

3

Planar Calculus

$P\mathcal{H}\mathrm{C}$

First, we propose planar calculus $P\mathcal{H}C$

.

The set ofinitial graphs in P7{Ccontains all graphs isomorphic

to $K_{4}$

.

There

are

four rules, whereRules 1 to3

are same

as thesystem $\prime HC$, but edgeaddition and vertex

contraction

are

restricted

so

that theresulting graphsareplanar. Rule 4 isas follows:

4. Quadrilateral rule: Let $G_{3}$ beagraphwith vertex set $\{v_{1},$

\ldots ,$v_{n}\}$thatcontainsaface$v_{1}$,$v_{2}$,$v_{3}$,$v_{4}$

.

Let $G_{1}$ be a graphobtained by contracting vertices $v_{1}$ and $v_{3}$ of $G_{3}$. Let $G_{2}$ be a graph obtained by contracting vertices$v_{2}$ and $v_{4}$of $G_{3}$

.

Then from

G}

and $G_{2}$, we can construct the graph$G_{3}$ (See

Figure 1).

Rule4is important when given graph consists of only triangle and quadrilateral faces.

For example,

we

show that the graph $G_{3}$ ofFigure 2 has

a

construction in P7{C. Let $G_{1}$ and $G_{2}$ be

thegraphs shownin Figure 2. $G_{1}$ contains$K_{4}$

as

asubgraph induced by $\{v_{1},v_{2},v_{3},v_{5}\}$

.

$G_{2}$ also contains

15

Figure 1: $G_{1}$, $G_{2}$ and$G_{3}$ ofRule4 in$VHC$

Figure 2: Exampleof the system$P’HC$

constructedfrom $G_{1}$ and $G_{2}$ by Rule4, since$v_{1}$,$v_{2},v_{7},v_{6}$ is aquadrilateralfaceand $G_{1}$ is identical to $G_{3}$

with$v_{2}$ and$v_{6}$ contracted and$G_{2}$ isidentical to$G_{3}$ with $v_{1}$ and$v_{7}$ contracted.

Since$G_{3}$ isedgeminimalwith respectto the 3-colorability,$G_{3}$ cannotbeconstructeddirectlybyRule1.

Each face of$G_{3}$ is triangleorquadrilateral, thus there is not a triplet ofvertices$v$,$v’$,$v’$ of satisfying the

condition of Rule 2. Thismeansthat$G_{3}$ cannot be constructed directly by Rule 2. Contraction rulecannot

break the structure of non-3-co1orab1i1ity. Therefore, probably $G_{3}$ is anexampleof graphs that essentially

needRule 4 in$P\mathcal{H}C$

.

In therest of this section,weprove thesoundness andthe completeness of$PHC$

.

Theorem 2

VHC

is sound.

Proof: We only need to showthat Rule4issoundsinceotherrules alsoappearin$HC$and

are

showntobe

sound[3]. Assume that there existsa3-colorable graph$G_{3}$ generatedby Rule4. Then, itsface $v_{1}$,$v2,$$v3$,$v_{4}$

has acoloring satisfyingoneofthefollowingcases:

Case 1: $\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{1})=\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{3})$.

Case2: $\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{2})=$color(v4).

Note that, if neither of the

cases are

satisfied, wehave color$(v_{1})\neq \mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{3})$and $\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{2})\neq$color(v4).

In this case,

we

need

more

than four colorsto the face, which contradictsthe $3$-colorabilityof$G_{3}$. Cases1

(Case 2, respectively) implies that $G_{1}$ ($G_{2}$, respectively) is 3-colorable. Therefore, only non-3-c1orab1e

graphs

are

generated. $\square$

Theorem 3

VHC

is complete.

Proof: We prove this theorem by induction

on

the size $n$ of the graph. In

case

$n<4$, all graphs

are

colorablebyat most 3 colors. In

case

$n=4$, $K_{4}$ is the initial graph of$P\mathcal{H}C$. Other graphs of size4

are

all

3-colorable,so wedo notcarethem.

Assumethat allnon-3-co1orab1egraphsofsize n-l

can

beconstructed inP7{C. We

assume

that there

exists

a

nonempty set $\mathcal{G}$ofnon-3-co1orab1egraphs of size $n$that cannot be constructedin $PHC$

.

Thenwe

lead

a

contradiction that edge maximal graph $G\in Ci$ can beconstructed. By consideringthe size of the

faces in$G$,

we

havethefollowingthree

cases.

Case 1: All faces

are

triangle. According to Theorem 5 (we prove this theorem later), $G$ can be

constructed in$P\mathcal{H}C$

.

Case 2: Thereisa face$f$of size$k\geq 5$. Let$v_{1},v_{2},v_{3},v_{4}$,$\ldots$,$vk$bethevertices offace$f$

.

$G’=G+(v_{1},v\mathrm{s})$

and$G’=G+(v_{1}$,$v_{4}\rangle$canbe constructed, since$G$isaedge maximal graphin

$\mathcal{G}$

.

Therefore

we can

construct

Figure 3: $G_{n}$

Case 3: $G$is composed of triangle

or

quadrilateral faces. Let $f=v_{1}$,$v_{2}$,$v\mathrm{s}$,v4 be a quadrilateral face

of$G$

.

Let $G’$ be a graph obtained by contracting vertices$v_{1}$ and$v_{3}$ of$G$. Let $G’$ be agraphobtained by

contracting vertices $v_{2}$ and $v_{4}$ of G. $G’$ and $G’$ can be constructed in $P’HC$ because of the assumption.

Thereforewe canconstruct $G$ from $G’$ and $G’$ aPPlying the Rule4.

In any case, $G(\in \mathcal{G})$ can be constructed in$PHC$, which contradict to the definition of $\mathcal{G}$. Thus, any

non-3-co1orab1egraphcanbe constructed in$PHC$. $\square$

Now, we prove that any triangulate non-3-co1orab1e planar graph can be constructed in polynomial

number ofsteps. Firstweprove the followinglemma,whichconstruct anessential component of triangulate

planargraphs.

Lemma 4 Lei$G_{n}=(V,$E) be a graph

of

3n$+1$ vertices, wheren$\geq 1$,

$V=\{a\mathrm{o}\}\cup$ $\{a_{i}, b_{t}, c_{i}|\mathrm{i}\in\{1, \ldots, n\}\}$,

$E=\{(a_{\mathit{0}}, a_{n})\}\cup\{(a_{\mathrm{i}-1}, b_{i}), (a_{i-1}, \mathrm{c}_{l}), (a_{i}, b_{i}), (a_{i},c_{i}), (b:, c_{l})|\mathrm{i}\in\{1, \ldots, n\}\}$

then, $G$ has a linearsize constr uction in _$PHC$.

PROOF: We prove this lemma byinduction

on

$n$

.

In

case

$n=1$, the lemma obviously holds since $G_{1}$ is

isomorphictoan initialgraph$K_{4}$

.

We prove that $G_{n}$ can be constructed by the assumptionthat $G_{n-1}$ can be constructed. $G’=G_{n}+$

$(a_{0},a_{n-1})$ canbeconstructedin$VHC$since$G_{n-1}$is subgraph of$G’$. $G’=G_{n}+(a_{n-1},a_{n})$canbeconstructed

in$PHC$sincesubgraphof$G’$induced by$\{a_{n-1}, a_{n}, b_{n}, c_{n}\}$ isisomorphic to $K_{4}$

.

Therefore we can construct $G_{n}$ by applyingRule 2 to $G’$ and$G’$. Since

we

applyRule 1 twiceand Rule 2 once at each inductionstep,

the whole construction is linearly bounded. $[]$

Theorem 5 fflangutate non-3-colorableplanargraphs have apolynomial size construction in PHC.

Proof: Ourgoalisto finda structure$G_{n}$ of Lemma4

as

a subgraph of a givengraph$G$. We try to assign

colorsto verticesof$G$

.

Initially, we choose atriangle face$\mathrm{u}\mathrm{i}$,

$v_{2}$,$v_{3}$ andassigndifferent color toeachvertex, color$(v_{1})$ $=R$, $\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{3})=G$ and$\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{3})=B$

.

We introduce three trees $T_{R}$,$Tc$,$T_{B}$

.

The root node of

each tree is one of the vertices $\mathrm{u}\mathrm{i}$,

$v_{2}$,$v_{3}$. The face that its vertices

are

already assigned a color is called

a colored face. Next, we repeat the following procedure until allvertices

are

assigned acolor

or

adjacent

vertices are assignedthe

same

color. Choose

a

non-colored triangle face$f’$ adjacent to coloredface $f$

.

We

need not to think about thecase that non-coloredfaces exist but

are

not adjacentto colored facebecause

thegiven graphisconnectedandtrianglate. Let$v$ be avertex that belongs to$f$ anddoesnot belongto $f’$.

Let$v’$ be avertexthat belongsto $f’$and does not belong to $f$

.

Vertices $v$and $v’$

are

uniquely determined.

Thenweassign$c=$color(v) to$v’$ and addthevertex$v’$to thetree$T_{\mathrm{c}}$as a child node of$v$

.

Thisreplication

stopsbefore all vertices assigned acolor because $G$ is non-3-co1orab1e. When the repetition stops,

we

find

adjacent vertices $v’$ and$v’$

on

$G$that areassigned the

same

color$c$

.

The tree$T_{c}$includes$v’$ and $v’$

so

that

there is

a

path$p$from$v’$ to $v’$in$T_{c}$. AnEdge $(v_{i},v_{j})\in T_{\mathrm{c}}$corresponds to a subgraphof$G$asthe Figure4.

Let $G’$ beasubgraphof$G$that corresponds to path_$p$ ($G’$ ofFigure 5 isan example) that correspondsto

path$p$ (dotted line ofthefigure). Let $G’$ beagraph$G|p|$ ofLemma 4. $G’$ can beconstructed because of

Lemma 4. $G’$

can

be constructed from$G’$ with

some

vertices contracted. $G$

can

be constructedfrom$G’$ by

17

Figure4: Relationbetween$v_{i}$ and$v_{g}$ in $G$

Figure 5: Subgraph of$G$and itsstructure

4

Planar

Calculus

PHC’

Inthis section,

we

propose another planarcalculus $P\mathcal{H}C^{*}$. The set ofinitial graphs in $PHC^{*}$ contains all

graphs isomorphic to $K_{4}$. Therearethreerules for generating newgraphs. Rule 1 and Rule 3are same as

thesystem$P?\{C$. Our new Rule2 isas follows:

2. Vertex $\mathrm{d}\mathrm{i}\mathrm{v}\mathrm{i}\mathrm{s}\mathrm{i}\mathrm{o}\mathrm{n}/\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}$ elimination rule: Let $G_{1}$ be a graph with $n$ vertices $\{v_{1}, \ldots, v_{n}\}$ that

contains anedge $(v_{1},v_{2})$, and$G_{2}$ be thegraphobtainedby contracting$v_{1}$ and$v_{2}$of$G_{1}$.Then from$G_{1}$

and$G_{2}$, we

can

construct agraph$G_{3}$ graphthat

are

identical to$G_{1}$ but does not contain $(v_{1}, v_{2})$

.

Rule 2 is simple but powerful $|\mathrm{t}\mathrm{o}$ generate non-3-co1orab1e graphs. This rule

means

that none adjacent

vertices$v1$ and$v_{2}$

can

be assigned the same color

or

different colors.

In the rest ofthissection, weprove thesoundness and the completeness of$P\mathcal{H}C^{*}$.

Theorem 6 $PHC^{*}$ is sound.

Proof: We onlyneedto show the soundness ofRule 2 since other rules also appearin$HC$ and areshown

to besound [3], Assumethatthere exists

a

3-colorable graph$G_{3}$ generatedbyRule 2. Then,itsvertices$v_{1}$

and $v_{2}$ has acoloring satisfyingoneof thefollowing twocases:

Case1: $\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{1})\neq \mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{2})$

.

Case2: $\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{1})=\mathrm{c}\mathrm{o}1\mathrm{o}\mathrm{r}(v_{2})$

.

In Case 1, the coloring is also valid for$G_{1}$, i.e., $G_{1}$ is 3-colorable. In Case 2, wecan contract vertices

$v_{1}$ and $v_{2}$ in $G_{3}$, i.e., $G_{2}$ is also 3-colorable. Therfore, in $VHC$ , all graphs generated by Rule 2

are

non-3-co1orab1e $\square$

Theorem 7 $PHC^{*}$ is complete.

Proof: All non-3-co1orab1e planar graphscan be constructed in $VHC$

.

We

can

simulate $P\mathcal{H}C$ by$P\mathcal{H}\mathrm{C}^{*}$,

so that$P\mathcal{H}C^{*}$ is complete. $\square$

5

Polynomial-Time Simulation

We show the relationship betweenP7{C and P7{C*. First directionis thatwe simulate

VHC

by$P\mathcal{H}C^{*}$

.

Theorem 8 $PHC^{*}p$-simulatesVHC.

Proof: Rules 1 and 3 are

common

in $P\mathcal{H}C^{*}$ and $PHC$

.

We only need to simulate Rule 2 and Rule4 in

$PHC$ by$P$}$tC^{*}$. Accordingto Lemma 9 Rule 2 canbesimulated. According toLemma 10, Rule4 canbe

simulated. In each case the series of simulating steps

can

be constructed in polynomial time. Therefore,

$PHC$’

$P$-simulates$VHC$

.

$\square$

Lemma 9 $PHC^{*}p$-sirnulates Rule 2

of

PHC.

Proof: We prove that agraph$G_{3}$

can

be constructed from $G_{1}$ and $G_{2}$ in$PHC^{*}$. Let $G_{1}$ and $G_{2}$ be two

graphswith

common

vertexset $\{v_{1}, \ldots, v_{n}\}$ which are identicalexcept that $G_{1}$ contains edges $(v1, v2)$ and

$(v_{2}, v_{3})$ andnot $(v_{1},v_{3})$, whereas$G_{2}$ contains edges $(v_{1}, v_{2})$ and $(v_{1},v_{3})$ andnot $(v_{2},v_{3})$

.

$G_{3}$ isidenticalto

$G_{1}$ but does not contain $(v_{2}, v_{3})$. Let$G_{1}’$ beagraph identicalto$G_{1}$ withvertices$v_{1}$ and$v_{3}$

are

contracted.

$(G_{1}, G_{1}’, G_{2}, G_{3})$ isasubsequenceofaconstructionin$P?t\mathrm{C}^{*}$ since$G_{1}’$

can

beconstructedfrom$G_{1}$ byRule3 and $G_{3}$ can beconstructed from$G_{1}’$ and$G_{2}$ by Rule 2 with paticular vertices$v_{1}$ and$v_{3}$. [Il

Figure6: $G_{1}$, $G_{2}$ and$G_{3}$ of Rule4in$P\mathcal{H}C$

Figure 7: Intermediategraphs of simulation in $PHC^{*}$

Lemma 10 $P\mathcal{H}C$” _$p$-sirrvulates Rule

4

of

PHC.

PROOF: Let Gi,$G_{2}$ and $G_{3}$ be graphs

as

Figure6. $G_{3}$ isagraph withvertex set $\{v_{1}, \ldots,v_{n}\}$that contains

aface$v1$,$v_{2}$,$v_{3}$,$v_{4}$. $G_{1}$ is agraph obtained bycontractingvertices$v_{1}$ and$v3$ of$G_{3}$

.

$G_{2}$ isagraphobtained by contractingvertices$v_{2}$ and$v_{4}$ of$G_{3}$. We prove that agraph$G\mathrm{s}$canbe constructed from $G_{1}$ and $G_{2}$ in

$PHC^{*}$

.

Let $G_{1}’$ be the graph as Figure 7. $G_{1}’$ is identical to $G_{1}$, but has two additionalvertices $u$ and $w$

andthree additional edges $(v_{1}, u)$,$(v_{1}, w)$,$(u, w)$

.

$G_{1}’$

can

beconstructed ffom $G_{1}$ by Rule 1, since $G_{1}’$ is a

subgraph of$G_{3}’$

.

Let $G_{3}’$, $G_{3}’$ and $G_{3}’$ be graphs asFigure 7 that are identical to $G_{3}$ but someverticesand

edgesinthe figureisdifferent from$G_{3}$. $G_{3}’$canbe constructed from$K_{4}$byRule 1 sinceasubgraphinduced

by $\{v_{1}, v_{3}, u, w\}$ is isomorphic to $K_{4}$

.

$G_{3}’$

can

be constructed from $G_{1}’$ and $G_{3}’$ by Rule 2 in $PHC^{*}$ with

paticularvertices$v_{1}$ and$v_{3}$ ($G_{3}’$ has

an

edge ($v_{1}$,$v_{3}$) and $G_{1}’$ is identical to $G_{3}’$ with $v_{1}$ and$v_{3}$ contracted).

$G_{3}’$

can

be constructed from $G_{3}’$by contractingtwo pairs of vertices $(v_{2}, u)$ and$(v_{4}, w)$

.

This construction

needs twice of applying Rule3in$P\mathcal{H}C^{*}$

.

Then $G_{3}$ can beconstructed from$G_{3}’$and $G_{2}$ byRule 2in$P\mathcal{H}C^{*}$

with paticularvertices u2 and $v_{4}$. Thus Rule4 in$PHC$canbepsimulated by$P\mathcal{H}C^{*}$.

$\square$

Theorem 8implies thatthe modifiedrule (Rule 2) isat least

as

powerfulas the original

one

in $HC$

.

Corollary 11 $\mathcal{H}C$ can bep simulate by$PHC^{*}$ without planarity ristiction on the inter mediate graphs.

It is difficultto show that$VHC$psimulates$PHC^{*}$

.

For example,as shown in Figure 8, Rule2 in$PHC$”

cangeneratea newquadrilateral of$G_{3}$ from $G_{1}$ and $G_{2}$. To simulatethis construction we must

remove an

edge$(v_{2}, v_{4})$ of$G_{1}$ by rulesin$VHC$, but edge elimination rulecannotbeappliedsince ($v_{2}$,V4)

are

sandwiched

between triangle faces andtheother rules cannotelim inate edges.

19

6

Concluding Remarks

We showthat there existasystem of generatingnon-3-co1orabIeplanar graphs,where intermediate graphs

in the system

are

restricted to be planar. Two calculi $PHC$ and $P\mathcal{H}C^{*}$ are sound and complete graph

construction system thatgeneratesthe class of non-3-co1orab1eplanargraphs. $PHC^{*}$is simple butpowerful

calculus, since$PHC$”_{psimulates$VHC$}

.

Relationship between construction in planar graph calculus and general graph calculus may be

inter-esting. There is a structure that can replace crossing edges keeping the colorability condition,

so

that

non-planar graphs

can

be mapped to planar graphs. Thus a class ofgraphs that have super-polynomial

lower bound in $HC$ may be associated with a class of graphs in a planar calculus. For future discussion,

wewouldliketo considerpolynomial-time simulation of$P\mathcal{H}C^{*}$ by$PHC$. Also lowerbound of planar graph

calculusis

an

interestingwork.

References

[1] H. HADWIGER, “Uber eine Klassifikation der Streckenkomplexe,” Vierteljahrsschr Naturforsch, Ges.

Zurich, 88, _PP.133-142 (1943)

[2] G. A. DiRAC, “A propertyof 4-chromatic graphs and some remarks

on

critical graphs,” J. London

Math. Soc, 27, PP.85-92, (1952)

[3] G. HAJO’S, $”\ddot{\mathrm{U}}$ver

eine Konstruktionnicht $n$-f\"arbbarer Graphen,” Wiss. ZeitschrMartin LutherUniv.

Halle-Wittenberg, A 10 (1961)

[4] K. WAGNER, “Beweis einer Abschwichung der Hadwiger Vermutung,” Math. Ann., 153, pp.139-141

(1964)

[5] R. M. KARP, “Reducibilityamong CombinatorialProblems,” Proc. Symp. Complexity of Computer

Computations, Ed. R. E. MILLER, J. W. THATCHER, pp.85-103 (1972)

[6] S. A. Cook AND R. A. RECKHOW, “Time bounded random

access

machines,” Journal of Computer

and System Sciences, 7 (4),

_PP.354-375

(1973)

[7] K. APPELANDW. HAKEN, “Every planarmapisfourcolorable,” Part I: Discharging, Illinois J.Math.,

21, pp.429-490 (i977)

[8] K. APPEL, W. HAKEN, AND J. Koch, “Every planar map is four colorable,” Part II: Reducibility,

Illinois J. Math., 21, pp.491-567 (1977)

[9] M. R. GAREY AND D. S. JOHNSON, “Computers and Intractability: A guide to the theory of

NP-Completeness,” W. H. FREEMAN, (1979)

[10] F. GUTHRIE, “Noteon the colouringof maps,” Proc. R. Soc. Edinb., 10, pp.727-728 (1980)

[11] A. J. MANSFIELD, D. J. A. Welsh, “Some coloring problems and their complexity,” Annals of

Discrete Mathematics, 13 (1982)

[12] K. APPEL AND W. HAKEN, “EveryPlanar Mapis FourColorable, Providence,” RhodeIsland,AMS,

(1989)

[13] T. PiTASSl, P. W. BEAME, AND R. IMPAGLIAZZO, “Exponential lower bounds for the pigeonhole

principle,” Computational Complexity, 3 (2), pp.97-140 (1993)

[14] M. AJTAI, “The complexity of the pigeonhole principle,” Combinatorica,14 (4), _{pp.417-433 (1994)}

[15] T. R. JENSEN AND B. Toft, “Graph Coloring Problems”, Wiley (1995)

[16] T. PITTASI AND A. URQUHART, “The complexity of the Hajos Calculus,”

SIAM

Journal on Discrete

Mathematics, Vol. 8 (1995)

[17] K. IWAMA$\Lambda \mathrm{N}\mathrm{D}$T. PITASSIRT,

$\iota$‘

Exponentiallower bounds for the treelikeHajosCalculus” Information

Processing Letters, Vol. 54, PP. 289-294 (1995)

[18] J. $\mathrm{K}\mathrm{R}\mathrm{A}\mathrm{J}\acute{\mathrm{I}}\check{\mathrm{C}}\mathrm{E}\mathrm{K}$, P.

PUDL\’AK,

AND A. Woods, “Exponentiallower bounds to thesizeof bounded depth

Frege proofs of the pigeonhole principle,” Random Structures and Algorithms, 7 (1) (1995)

[19] N. ROBERTSON, D. SANDERS, P. D. SEYMOUR,ANDR.Thomas, “The four-colourtheorem,” J.