Algorithms And Complexity Of Conditional Coloring

The graph coloring theory has a central position in discrete mathematics. It appears in many places with seemingly no or little connection to coloring. The graph coloring theory is also of interest for its applications. Time tabling, sequencing, and scheduling problems, in their many forms, are basically of this nature.Let graph G be G=(V(G),E(G)). For a positive integer k, a proper k-coloring of a graph G is a surjective mapping c:V(G)→{1,2,..., k} with the property that ifμand v are neighbors in G, then c(μ)≠c(ν). The smallest k such that G has a properκ-coloring is the chromatic number of G, denoted byχ(G). For a subset S of V(G), we use c(S) to denote{c(u)|μ∈S}.By now the graph coloring has many generalizations. The edge coloring, the listing coloring, the face coloring and the total coloring etc.The conditional coloring we have researched is a generalization of the tradi-tional coloring. For integers k> 0 and r> 0, a proper (k,r)-coloring of a graph G is a surjective mapping c:V(G)→{1,2,...,κ} such that both of the following two conditions hold: (C1) ifμ,ν∈V(G) are neighbors in G, then c(μ)≠c(ν); (C2) for anyν∈V(G),|c(NG(ν))|≠min{d(ν),r}.For a given integer r> 0, the smallest integerκ> 0 such that G has a proper (κ,r)-coloring is called the rth-order conditional chromatic number of G, and is denoted by Xr(G).By the definition ofχr(G), it follows immediately thatχ(G)=χ1(G), and so conditional coloring is a generalization of traditional graph coloring. The conditional chromatic number has a very different behavior from the traditional chromatic number. In 2006, Lai, Lin, Montgomery, et al. gave many basic propositions and theorems on the new coloring which showed many differences. In this thesis, we focus on the computational aspect of the problem. This thesis has three parts. The first part contributes to the computational aspect of the conditional colorability of general graphs. The second part con-tributes to the 2nd-order conditional 3-coloring of claw-free graphs. The third part contributes to some other propositions and results on the conditional chro-matic number.The first part consists of Chapters 2 and 3. In Chapter 2, we are interested in the complexity of conditional colorability of general graphs. Our main result is that conditional (3,2)-colorability remains N P-complete when restricted to planar bipartite graphs with maximum degree at most 3 and arbitrarily high girth. This differs considerably from the well-known result that traditional 3-colorability is polynomially solvable for graphs with maximum degree at most 3. We also prove that some other well-known complexity results for traditional coloring still hold for conditional coloring. In Chapter 3, we will show that (3,2)-colorability is polynomially solvable for graphs with bounded tree-width. And we will also give a polynomial time algorithm using at mostΔ(G)+1 colors to color the graph G properly for r=2 whenΔ(G)≥4.The second part is Chapter 4. In this part, we investigate the 2nd-order con-ditional 3-colorings of claw-free graphs. First, we prove that it is N P-complete to determine if a claw-free graph with maximum degree 3 is 2nd-order condition-ally 3-colorable. Second, by forbidding a kind of subgraphs, we find a reasonable subclass of claw-free graphs with maximum degree 3, for which the 2nd-order conditionally 3-colorable problem can be solved in linear time. Third, we give a linear time algorithm to recognize this subclass of graphs, and a linear time al-gorithm to determine whether it is 2nd-order conditionally 3-colorable. We also give a linear time algorithm to color the graphs in the subclass by 3 colors.The third part is Chapter 5. In this part, we will give some other propositions and results on the conditional chromatic number.