目录 Contents Chapter 1 Acyclic Coloring 1 1.1 Basic Definitions and Notations 1 1.2 Acyclic Vertex Coloring 1 1.3 Generalized Acyclic Vertex Coloring 10 1.3.1 r-acyclic Vertex Coloring 11 1.3.2 Degenerating Coloring 17 1.4 Acyclic Edge Coloring 29 1.5 Open Problems 47 Reference 47 Chapter 2 Neighbor Sum Distinguishing Coloring 51 2.1 Basic Definitions and Introduction 51 2.2 Neighbor Sum Distinguishing Edge Coloring of Graphs 52 2.2.1 The Conjecture and Related Results 52 2.2.2 The List Version of Neighbor Sum Distinguishing Edge Colorings 75 2.3 Neighbor Sum Distinguishing Total Coloring of Graphs 76 2.3.1 The Conjecture and Related Results 76 2.3.2 Neighbor Sum Distinguishing Total Choosability of Graphs 78 2.4 Equitable Neighbor Sum Distinguishing Coloring 86 Reference 87 Chapter 3 Edge Cover Coloring 91 3.1 The Edge Cover Coloring of Graphs 91 3.1.1 Edge Cover Chromatic Index and Classi-cation of Graphs 91 3.1.2 Edge Covered Critical Graphs 97 3.1.3 Unsolved Problems on Edge Cover Coloring 102 3.2 Fractional Edge Cover Coloring of Graphs 102 3.2.1 Introduction 103 3.2.2 Main Results on Fractional Edge Cover Coloring of Graphs 105 3.2.3 The Conjectures and Discussions on Fractional Edge Cover Coloring 109 3.3 g-edge Cover Coloring of Graphs 110 3.3.1 g-edge Cover Chromatic Index of Graphs 111 3.3.2 g-Edge Covered Critical Graphs 113 3.3.3 Related Problems on g-edge Cover Coloring of Graphs 121 Reference 122 Chapter 4 f-colorings of Graphs 124 4.1 Introduction 124 4.2 Basic Definitions and Tools 125 4.3 f-colorings of Multigraphs 127 4.4 The Classification Problem of Simple Graphs on f-Colorings 131 4.4.1 Main Results 133 4.4.2 Application in Proper Edge Colorings of Simple Graphs 140 4.4.3 Further Discussion 143 4.5 Critical Graphs on f-colorings 144 4.5.1 Some Properties of f-critical Graphs 145 4.5.2 Bounds on the Number of Edges of f-critical Graphs 148 4.5.3 f-regular f-critical Graphs 151 4.5.4 f-critical Graphs with The f-core Having Maximum Degree 2 153 4.5.5 Some problems for future research 159 4.6 Equitable Edge-colorings of Simple Graphs 160 4.6.1 A Useful Lemma 163 4.6.2 A Problem for Further Research 184 Reference 185 Chapter 5 Total Coloring 188 5.1 Introduction 188 5.2 Total Coloring Conjecture and the Related Results on *≥9 188 5.2.1 Total Coloring Conjecture 188 5.3 Total Coloring of Graph G with *(G) ≤8 202 5.3.1 The Results on the Case*≤8 202 5.3.2 The Results on the Case*≤7 220 5.4 List Total Coloring of Graphs 234 5.5 The Open Problems and Conjectures 243 Reference 243 Index 247
内容摘要 Chapter 1
Acyclic Coloring
1.1 Basic Definitions and Notations
A proper k-coloring of a graph G is a mapping * from V (G) to the set of colors {1; 2; ; k} such that for any edge xy of G. A proper coloring of a graph G is acyclic if there is no 2-colored cycle in G, in other words, if the union of any two color classes induces a subgraph of G which is a forest. The acyclic chromatic number of G, denoted by Xa(G), is the smallest integer k such that G has an acyclic k-coloring.
A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by X’a(G), is the least number of colors in an acyclic edge coloring of G.
1.2 Acyclic Vertex Coloring
Acyclic colorings of graphs were introduced by Gr.unbaum. In 1973, Gr.unbaum posed the following conjecture.
Conjecture 2.1[24] For any graph G with maximum degree,
In the same paper, he proved that Conjecture 2.1 holds for.
In 1979, Borodin [8] proved Gr.unbaum s conjecture partially that every planar graph is acyclically 5-colorable. This bound is best possible. Moreover, Fertin et al. have shown that there are bipartite 2-degenerate planar graphs that are not acyclically 4-colorable[19]. In [33], Kostochka proved that for every k ≥ 3, the problem of deciding whether a graph is acyclically k-colorable is NP-complete. Alberson et al.[1] proved that every toroidal graph is acyclically 8-colorable. In 1978, Kostochka[32] proved that if, then.
In the process of proofing Conjecture 2.1, Albertson and Berman mentioned that Erdos proved that, then they proposed the following conjecture.
Conjecture 2.2 ([1]) For any graph G with maximum degree ,
In 1991, Alon et al. gave an upper and lower bounds for acyclic chromatic number of general graph.
Theorem 2.3 ([3]) For any graph G,
This theorem proved Conjecture 2.1 was wrong. For graphs with, Fertin et al. gave the following result.
Theorem 2.4 ([19]) Let G be a graph with maximum degree. Then.
In 2009, K.Kothapalli et al. gave the following result.
Theorem 2.5 ([35]) Let G be a graph with maximum degree . Then
Recently, D.Goncalves et al. employ entropy compression method to prove the following Theorem.
Theorem 2.6 ([22]) Let G be a graph with maximum degree . Then
In order to get an improved upper bound of acyclic chromatic numbers of graphs, in [11], Cai, Feng and Yan found a class of graphs with some girth restrictions whose acyclic chromatic numbers are linear in its maximum degree. Actually, we obtain the following result.
Theorem 2.7 ([11]) Let G be a graph with maximum degree and girth. Then.
Proof We make use of the Lov.aze Local Lemma as our important tool in the proof of the Theorem. Before the proof, we state the general version of the Lovaze Local Lemma as follows.
Lemma 2.1 ([38]) Let A1,A2; ,An be events in an arbitrary probability space. Let the graph H = (V;E) on the nodes {1, 2, ,n} be a dependency graph for the events Ai; that is, assume that for each i, Ai is independent of the the family of events. If there are reals such that for all i,
then
Proof of Theorem 2.7 Let G = (V,E) be a graph of size m. Our aim is to prove that there exists a coloring of vertices of G, f :; kg such that f satisfies the following two properties.
(i) every two adjacent vertex have di.erent colors;
(ii) there are at least 3 colors in every cycle C of G.
Then we obtain an acyclic coloring of G.
For each vertex, first we do the following random coloring. Put. Then let f : {} be a random vertex coloring of G, where for each vertex, the color is chosen randomly and independently according to a uniform distribution on {1,2, ,x}.
For the sake of using Lemma 2.1(Local Lemma), we consider the following two types of bad events.
Type I For each pair of adjacent vertices u and v of G, let Au;v be the event that f(u) = f(v).
Type II For each even cycle C, we say that event AC occurs if C receives two colors under the random coloring f. If the length of cycle C is i, then such an event is called an event of type i.
Then we obtain the following proposition.
Proposition 2.1 If no event of Type I or Type II occurs, then f is an acyclic coloring satisfying properties (i) and (ii).
It is obvious that Proposition 2.1 is true. In the following we will show that with positive probability none of these two kinds of bad events happens, then we can apply the Local Lemma 2.1 to prove Theorem 2.7.
Let us construct the dependency graph H needed in Lemma 1. We use X to denote the set that consists of two adjacent vertices in G colored by the same color in random coloring f, or an even cycle in G which is colored by 2 colors in randomcoloring f. Let V (H) ={}is an event of Type I or Type IIg. For each pair of nodes AX;AY ∈ V (H), AX and AY are adjacent if and only if . Since the
以下为对购买帮助不大的评价