Published on

28-Dec-2016View

213Download

1

Embed Size (px)

Transcript

The -perfection of graphs

G. Araujo-Pardo 1,2

Instituto de MatematicasUniversidad Nacional Autonoma de Mexico

Campus Juriquilla, Mexico

C. Rubio-Montiel 3

Instituto de MatematicasUniversidad Nacional Autonoma de Mexico

Ciudad Universitaria, Mexico

Abstract

In this paper we study a natural generalization for the perfection of graphs to otherinteresting parameters related with colorations. This generalization was introducedpartially by Christen and Selkow in 1979 and Yegnanarayanan in 2001.Let a, b {, ,, , } where is the clique number, is the chromatic number,

is the Grundy number, is the achromatic number and is the pseudoachromaticnumber. A graph G is ab-perfect if for every induced subgraph H, a(H) = b(H).In this work we characterize the -perfect graphs.

Keywords: Perfect graphs, Grundy, achromatic and pseudoachromatic numbers.

1 Research supported by CONACyT-Mexico under Project 166306 and PAPIIT-Mexicounder Project IN101912.2 Email: garaujo@matem.unam.mx3 Email: christian@matem.unam.mx

Available online at www.sciencedirect.com

Electronic Notes in Discrete Mathematics 44 (2013) 163168

1571-0653/$ see front matter 2013 Elsevier B.V. All rights reserved.

www.elsevier.com/locate/endm

http://dx.doi.org/10.1016/j.endm.2013.10.025

1 Introduction

Let G be a simple graph. A vertex coloring : V (G) {1, . . . , k} is calledcomplete if each pair of dierent colors appears in an edge. The pseudoachro-matic number (G) is the maximum k for which a complete coloring of Gexists.

A vertex coloring of G is called proper if uv is an edge of G then (u) =(v). The achromatic number (G) is the maximum k for which a proper andcomplete coloring of G exists.

A vertex coloring of G is called Grundy if it is a proper vertex coloringsuch that, for every two colors {i, j} Z+ with i < j, every vertex colored jhas a neighbor colored i. Consequently, every Grundy coloring is a completecoloring. The Grundy number (G) is the maximum k for which a Grundycoloring of G exists.

Clearly,(G) (G) (G) (G) (G) (1)

where (G) denotes, as usual, the clique number of G and (G) denotesthe chromatic number.

2 2 3 3 31

u1

2

u2

3

u3

1

u4

Fig. 1. A complete and proper coloring of P4 with 3 colors.

The Grundy number was introduced by Grundy in 1939, the achromaticnumber by Harary, Hedetniemi and Prins in 1967 and the pseudoachromaticnumber by Gupta in 1969.

Let a, b {, ,, , }. A graph G is called ab-perfect if for every inducedsubgraph H of G, a(H) = b(H). This denition extends the usual notion ofperfect graph introduced by Berge in 1961; with this notation a perfect graphis called -perfect. This reference and the following do not appear in thebibliography due to space restriction. Lovasz proved in 1972 that G is -perfect if and only if Gc is -perfect, where Gc denotes the complement ofG (that is, if G is a graph of order n, then V (Gc) = V (G) and E(Gc) =E(Kn) E(G)). Chudnovsky, Robertson, Seymour and Thomas proved in2006 that G is -perfect if and only if G and Gc are C2k+1-free for all k 2 4 ;and Seinsche proved in 1974 the following theorem which we will use to proveour Theorem 2.1:

4 A graph G without an induced subgraph H is called H-free. A graph H1-free, H2-free,. . . , Hm-free is called (H1, H2, . . . , Hm)-free.

G. Araujo-Pardo, C. Rubio-Montiel / Electronic Notes in Discrete Mathematics 44 (2013) 163168164

Theorem 1.1 (Seinsche, 1974) If a graph G is P4-free then G is -perfect.

The concept of the ab-perfect graphs was introduced in [3] and extendedin [5], but in this paper only was considered ab-perfect graphs for a, b {, , , }. The following statements are given in [5]:Theorem 1.2 (Yegnanarayanan, 2001) For any nite graph G the followingare equivalent:

1 G is -perfect,2 G is -perfect,3 G is -perfect4 G is C4-free.Corollary 1.3 (Yegnanarayanan, 2001) Every -perfect graph is -perfect.

Corollary 1.4 (Yegnanarayanan, 2001) Every -perfect graph is -perfect.

Unfortunately, this theorem is false (a counterexample is P4 because itis C4-free but not -perfect, see Figure 1); i.e., 4 does not necessarilyimply 1. Consequently the corollaries are not well founded, however, whileCorollary 1.3 is false (again the counterexample is P4, see Figure 1), Corollary1.4 is true (see Theorem 2.1). Note that if a graph G is -perfect then it isimmediately -perfect (see Equation 1). That is, G is perfect in the usualsense and it is well known that G does not allow odd cycles (except triangles)or their complements and then the condition C4-free is not sucient. InAppendix 4 of [2] we exhibit the exact place where the proof of the Theorem1.2, given by Yegnanarayanan, is wrong.

In this paper we examine this theorem. In the next section we will statesome theorems that characterize the -graphs. Also, we will show a graphG that has all of these parameters dierent, and we will exhibit, using adirected transitive graph D, the relationship between the ab-graphs for a, b {, , , }.

There exists interesting results related with these invariants; the authorsof this paper and others have studied some specic -perfect graphs: theline graph of the complete graph Kn for some specic values of n and theirrelation with the projective planes. For more information on this topic see [1]and the references therein.

As background to this paper, in [4] was proved that for any graph G andfor every integer a with (G) a (G), there is a complete and propercoloring of G with a colors. In [3] the authors proved that for any graph Gand for every integer b with (G) b (G) there is a Grundy coloring of

G. Araujo-Pardo, C. Rubio-Montiel / Electronic Notes in Discrete Mathematics 44 (2013) 163168 165

a)

G

v0

1v1

1v2

1v3

3

v4

1 v5

3

v62

v7

1

v8

2

v9

4v10

2v11

2v12

2b)

G

v0

1v1

2v2

2v3

2

v4

1 v5

2

v65

v7

3

v8

4

v9

5v10

4v11

3v12

5

Fig. 2. Dierent coloration of G.

G with b colors. Also, they give characterizations of a-perfect graphs whena is or (see [3]).

Yegnanarayanan, Balakrishnan and Sampathkunar proved in 2000 that if2 a b c there exists a graph G with chromatic number a, achromaticnumber b, and pseudoachromatic number c. Finally, Chartrand, Okamoto,Tuza and Zhang proved in 2010 that for integers a, b and c with 2 a b cthere exists a connected graph G with (G) = a, (G) = b and (G) = c ifand only if a = b = c = 2 or b 3.

2 Results

To start this section we show graph G, depicted in Figure 2, with all of theseparameters being dierent. In particular G has (G) = 2, (G) = 3, (G) =4, (G) = 5 and (G) = 6. The graph G is constructed as follows: Let e1be an edge of K4,4 and let e2 be an edge of C7, identifying e1 with e2 weobtain G. For construction, G does not contain C3 as an induced subgraph,then (G) = 2. Figure 2a) shows a proper vertex coloring of G with threecolors (black, white and gray), then (G) 3,, and G contains a C7 then(G) = 3. Also to the left we show a Grundy vertex coloring of G with fourcolors (numbers), then (G) 4. Figure 2b) shows a complete and propervertex coloring of G with ve colors and (G) 5. The proof of (G) 4,(G) 5 and (G) = 6 are given in Appendix 4 of [2].

In Figure 3 we show a directed transitive graph D where the vertices ofD represent the classes of ab-perfect graphs and their label is ab respectivelyfor a, b {, ,, , }. If two classes are equal they dene the same vertex(see Theorem 2.1). If a class of ab-perfect graphs is contained in a class ofcd-perfect graphs then there is an arrow from vertex ab to vertex cd. To provethat D does not contain another arrow we have the following counterexamples:P4, C4, C5 and P3 K2.

Finally, here are the theorems that we prove in [2]:

G. Araujo-Pardo, C. Rubio-Montiel / Electronic Notes in Discrete Mathematics 44 (2013) 163168166

=

=

=

D

Fig. 3. Relationship between ab-perfect graphs with a, b {, ,, , }.

Table 1P4 is a counterexample in these cases.

Table 2C4 is a counterexample in these cases.

Table 3C5 is a counterexample in these cases.

Table 4P3 K2 is a counterexample in this cases.

Theorem 2.1 Let G be a graph and let a {, , }. G is a-perfect if andonly if G is a-perfect.

Theorem 2.2 G is a connected graph of order n (C4, P4)-free if and onlyif there exists a set of connected graphs {G1, . . . , Gk} for some k N also(C4, P4)-free andm Z+ such that G = Km

ki=1

Gi and GKm is disconnected

G. Araujo-Pardo, C. Rubio-Montiel / Electronic Notes in Discrete Mathematics 44 (2013) 163168 167

(if k 2) 5 .In the following two theorems we prove some equivalences between graphs.

Note that, in the hypothesis of Theorem 2.3, G is a connected graph, while inTheorem 2.4, G is any graph (not necessarily connected).

Theorem 2.3 For any connected graph G the following are equivalent:

1 G is -perfect,2 G is -perfect,3 G is (C4, P4, P3 K2, 3K2)-free, and4 G = Kn1 (Kn2 Kn3 n4K1) or G = Kn1 (G n2K1) for n1 Z+ and n2, n3, n4 N where G is a non complete connected graph and

(C4, P4, P3 K2, 3K2)-free.Theorem 2.4 For any graph G the following are equivalent:

1 G is -perfect,2 G is -perfect,3 G is (C4, P4, P3 K2, 3K2)-free, and4 G = Kn1 Kn2 n3K1 or G = G n2K1 for n1 Z+ and n2, n3 N,

where G is a non complete connected graph and (C4, P4, P3K2, 3K2)-free.

Acknowledgment

The authors want to thank the anonymous referees of LAGOS 2013 for theirkind help and valuable suggestions which led to an improvement of this note.

References

[1] G. Araujo-Pardo, J. J. Montellano, R. Strausz; On the pseudoachromatic indexof the complete graph; Journal of Graph Theory, 66 Issue 2 (2011) (8997).

[2] G. Araujo-Pardo, C. Rubio-Montiel; On -perfect graphs; In review.

[3] C. Christen and Selkow; Some perfect coloring properties of graphs, Journal ofCombinatorial Theory, Series B, 27 (1979) (4959)

[4] F. Harary, S. Hedetniemi, G. Prins; An interpolation theorem for graphicalhomomorphisms, Portugaliae Mathematica, 26 (1967) (453462).

[5] V. Yegnanarayanan; Graph colouring and partitions, Theoretical ComputerScience, 263 (2001) (5974).

5 For convenience, in this paper 0 N and denotes the joint of graphs.

G. Araujo-Pardo, C. Rubio-Montiel / Electronic Notes in Discrete Mathematics 44 (2013) 163168168

IntroductionResultsReferences