Catálogo de publicaciones - libros

A graph is path -colorable if it has a vertex -coloring in which the subgraph induced by each color class is a disjoint union of paths. A graph is path -choosable if, whenever each vertex is assigned a list of colors, such a coloring exists in which each vertex receives a color from its list.

It is known that every planar graph is path 3-colorable [Poh90, God91] and, in fact, path 3-choosable [Har97]. We investigate which planar graphs are path 2-colorable or path 2-choosable. We seek results of a “threshold” nature: on one side of a threshold, every graph is path 2-choosable, and there is a fast coloring algorithm; on the other side, determining even path 2-colorability is NP-complete.

We first consider maximum degree. We show that every planar graph with maximum degree at most 4 is path 2-choosable, while for ≥ 5 it is NP-complete to determine whether a planar graph with maximum degree is path 2-colorable.

Next we consider girth. We show that every planar graph with girth at least 6 is path 2-choosable, while for ≤ 4 it is NP-complete to determine whether a planar graph with girth is path 2-colorable. The case of girth 5 remains open.

We consider the problem of determining the minimum chromatic number of graphs and hypergraphs of large girth which cannot be mapped under a homomorphism to a specified graph or hypergraph. More generally, we are interested in large girth hypergraphs that do not admit a vertex partition of specified size such that the subhypergraphs induced by the partition blocks have a homomorphism to a given hypergraph. In the process, a general probabilistic construction of large girth hypergraphs is obtained, and general definitions of chromatic number and homomorphisms are considered.

A proper vertex coloring of a graph = () is acyclic if contains no bicolored cycle. A graph is acyclically -list colorable if for a given list assignment = {(): ∈ }, there exists a proper acyclic coloring of such that () ∈ () for all ∈ . If is acyclically -list colorable for any list assignment with |L(v)| ≥ for all ∈ , then is acyclically -choosable.

Let be a planar graph without 4-cycles and 5-cycles. In this paper, we prove that is acyclically 4-choosable if furthermore satisfies one of the following conditions: (1) without 6-cycles; (2) without 7-cycles; (3) without intersecting triangles.

We present a polynomial algorithm, implicit in the work of El-Zahar and Sauer, which inputs a 3-colouring of a categorical product of two graphs and outputs a 3-colouring of one of the factors. We raise a question about the existence of polynomial algorithms for colouring the vertices of some graphs in terms of intrinsic succint description of the vertices rather than in terms of the (exponential) size of the graph.

The study of circular chromatic number () of a graph , which is a refinement of its chromatic number, has been very active in the past decade. Many nice results are obtained, new techniques are developed, and connections to other fields are established. This paper presents a glimpse of the recent progress on this subject. Besides presenting the results, some of the ideas and tools in the proofs are explained, although no detailed proofs are contained.

We prove that the vertex set of any twin-free loopless multigraph has an embedding into some point set of some Euclidean space , such that the automorphism group of is isomorphic to the isometry group of globally preserving P.

Let be a nonbipartite quadrangulation of the projective plane. Youngs [You96] proved that cannot be 3-colored. We prove that for every 4-coloring of and for any two colors a and , the number of faces of , on which all four colors appear and colors a and are not adjacent on , is odd. This strengthens previous results that have appeared in [You96, HRS02, Moh02, CT04]. If we form a triangulation of the projective plane by inserting a vertex of degree 4 in every face of , we obtain an Eulerian triangulation of the projective plane whose chromatic number is 5. The above result shows that is never 5-critical. We show that sometimes one can remove two, three, or four, vertices from and obtain a 5-critical graph. This gives rise to an explicit construction of 5-critical graphs on the projective plane and yields the first explicit family of 5-critical graphs with arbitrarily large edge-width on a fixed surface.

It is shown that if a graph of vertices can be drawn on the torus without edge crossings and the maximum degree of its vertices is at most , then its planar crossing number cannot exceed , where c is a constant. This bound, conjectured by Brass, cannot be improved, apart from the value of the constant. We strengthen and generalize this result to the case when the graph has a crossing-free drawing on an orientable surface of higher genus and there is no restriction on the degrees of the vertices.

Regular maps are cellular decompositions of closed surfaces with the highest ‘level of symmetry’, meaning that the automorphism group of the map acts regularly on flags. We survey the state-of-the-art of the problem of classification of regular maps on a given surface and outline directions of future research in this area.

Graph colourings may be viewed as special constraint satisfaction problems. The class of -colouring problems enjoys a well known dichotomy of complexity — these problems are polynomial time solvable when ≤ 2, and NP-complete when ≥ 3. For general constraint satisfaction problems such dichotomy was conjectured by Feder and Vardi, but has still not been proved in full generality. We discuss some results and techniques related to this Dichotomy Conjecture. We focus on the effects of a new concept of ‘fullness’, and how it affects the complexity of constraint satisfaction problems and their dichotomy. Full constraint satisfaction problems may then be specialized back to graph colourings, yielding an interesting novel class of problems in graph theory, related to the study of graph perfection.