On edge colorings of 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that every 1-planar graph with maximum degree Δ?10 can be edge-colored with Δ colors.     

List edge and list total colorings of planar graphs without short cycles

Let G be a planar graph with maximum degree Δ(G). We use and to denote the list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that and if Δ(G)?6 and G has neither C₄ nor C₆, or Δ(G)?7 and G has neither C₅ nor C₆, where Ck is a cycle of length k.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.     

Oriented vertex and arc colorings of outerplanar graphs

A homomorphism from an oriented graph G to an oriented graph H is an arc-preserving mapping φ from V(G) to V(H), that is φ(x)φ(y) is an arc in H whenever xy is an arc in G. The oriented chromatic number of G is the minimum order of an oriented graph H such that G has a homomorphism to H. The oriented chromatic index of G is the minimum order of an oriented graph H such that the line-digraph of G has a homomorphism to H.In this paper, we determine for every k?3 the oriented chromatic number and the oriented chromatic index of the class of oriented outerplanar graphs with girth at least k.     

Oriented colorings of 2-outerplanar graphs

A graph G is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the outer face is outerplanar. The oriented chromatic number of an oriented graph H is defined as the minimum order of an oriented graph H^′ such that H has a homomorphism to H^′. In this paper, we prove that 2-outerplanar graphs are 4-degenerate. We also show that oriented 2-outerplanar graphs have a homomorphism to the Paley tournament QR₆₇, which implies that their (strong) oriented chromatic number is at most 67.     

The oriented chromatic number of Halin graphs

The oriented chromatic number of an oriented graph G is the minimum order of an oriented graph H such that G admits a homomorphism to H. The oriented chromatic number of an unoriented graph G is the maximal chromatic number over all possible orientations of G. In this paper, we prove that every Halin graph has oriented chromatic number at most 8, improving a previous bound by Hosseini Dolama and Sopena, and confirming the conjecture given by Vignal.     

A note on total colorings of 1-planar graphs

A 1-planar graph is a graph that can be drawn in the plane such that each edge is crossed by at most one other edge. In this paper we give an upper bound for the total chromatic number for 1-planar graphs with maximum degree at least 10.     

List edge multicoloring in graphs with few cycles

The list edge multicoloring problem is a version of edge coloring where every edge e has a list of available colors L(e) and an integer demand x(e). For each e, we have to select x(e) colors from L(e) such that adjacent edges receive disjoint sets of colors. Marcotte and Seymour proved a characterization theorem for list edge multicoloring trees, which can be turned into a polynomial time algorithm. We present a slightly more general algorithm that works also on odd cycles. A variant of the method leads to a randomized polynomial time algorithm for handling even cycles as well.     

Some results on acyclic edge coloring of plane graphs

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. The acyclic chromatic index of a graph G, denoted by α^′(G), is the minimum number k such that G admits an acyclic edge coloring using k colors. Let G be a plane graph with maximum degree Δ and girth g. In this paper, we prove that α^′(G)=Δ(G) if one of the following conditions holds: (1) Δ?8 and g?7; (2) Δ?6 and g?8; (3) Δ?5 and g?9; (4) Δ?4 and g?10; (5) Δ?3 and g?14. We also improve slightly a result of A. Fiedorowicz et al. (2008) [7] by showing that every triangle-free plane graph admits an acyclic edge coloring using at most Δ(G)+5 colors.     

Kolmogorov random graphs only have trivial stable colorings

In this paper, we prove that random graphs only have trivial stable colorings. Our result improves Theorem 4.1 in [Proc. 20th IEEE Symp. on Foundations of Comput. Sci., 1979, pp. 39-46]. It can be viewed as an effective version of Corollary 2.13 in [SIAM J. Comput. 29 (2) (2000) 590-599]. As a byproduct, we also give an upper bound of the size of induced regular subgraphs in random graphs.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).     

There exist oriented planar graphs with oriented chromatic number at least sixteen

We prove that there exist oriented planar graphs with oriented chromatic number at least 16. Using a result of Raspaud and Sopena [Inform. Process. Lett. 51 (1994) 171-174], this gives that the oriented chromatic number of the family of oriented planar graphs lies between 16 and 80.     

On transitive orientations with restricted covering graphs

We consider the problem of finding a transitive orientation of a comparability graph, such that the edge set of its covering graph contains a given subset of edges. We propose a solution which employs the classical technique of modular tree decomposition. The method leads to a polynomial time algorithm to construct such an orientation or report that it does not exist.     

On acyclic edge coloring of toroidal graphs

Let c be a proper edge coloring of a graph G. If there exists no bicolored cycle in G with respect to c, then c is called an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ and girth g. In Dong and Xu (2010) [8], Dong and Xu proved that G admits an acyclic edge coloring with Δ(G) colors if Δ?8 and g?7, or Δ?6 and g?8, or Δ?5 and g?9, or Δ?4 and g?10, or Δ?3 and g?14. In this note, we fix a small gap in the proof of Dong and Xu (2010) [8], and generalize the above results to toroidal graphs.     

Game chromatic number of graphs with locally bounded number of cycles

We consider the coloring game and the marking game on graphs with bounded number of cycles passing through any edge. We prove that the game coloring number of a graph G is at most c+4, if every edge of G belongs to at most c different cycles. This result covers two earlier bounds on the game coloring number: for trees (c=0) and for cactuses (c=1).