The Clique-transversal Sets And Clique-coloring In Graphs

The transversal theory is one of the main content in the hypergraph theory.The clique-transversal is a special case of the hypergraph-transversal. The clique-transversal has important application in the topology design of the networks.Researching the clique-transversal problem will reveal the property and structureof the graphs further. The clique-coloring of graphs is closely related to the clique-transversal and the vertex-coloring of graphs. Since there is not the concept ofcritical graphs for the clique-coloring, the research of the clique-coloring will bemore complicated than the usual vertex-coloring. In this dissertation we mainlydo some research on the clique-transversal problem and clique-coloring problem.In chapter II, we mainly research the clique-transversal problem. Firstly,we prove that the clique-transversal problem and clique independent set problemare NP-complete for a cubic planar graph G of girth3. Meanwhile we proposean approximation algorithm respectively for the two problems in cubic graphs.Secondly, we give a polynomial-time algorithm for the clique-transversal set prob-lem in claw-free graphs with Δ(G)≤4. Finally, we discuss the bounds of theclique-transversal number in planar graphs、claw-free graphs and so on.In chapter III, we mainly research the clique-coloring problem. Firstly, weprove that every claw-free planar graph, other than an odd cycle, is2-clique-colorable and we present a polynomial-time algorithm to find its2-clique-coloring.As an immediate consequence, we give a sharp upper bound on the clique-transversal number for claw-free planar graphs. Secondly, we prove that linegraphs with maximum degree at most seven, except odd cycles, are2-clique-colorable. In addition, a polynomial-time algorithm of clique-coloring problem isgiven in the line graphs with maximum degree at most seven. In chapter VI, we mainly research the cycle-transversal problem. Brandst¨adtet al. proved that finding a minimum cycle transversal in a perfect graph is NP-complete, even for bipartite graphs with maximum degree four. In this chapterwe give an illustration to show that the proof is incorrect. Here, we present acomplete proof of the result.