Search

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: (i) v = u, (ii) e = f, or (iii) edge vu is from the set {e, f}. An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. The minimum number of colors needed for incidence coloring of a graph is called the incidence chromatic number.

Let G be a cellular embedding of a multigraph in a 2-manifold. Two distinct edges e1, e2 ∈ E(G) are facially adjacent if they are consecutive on a facial walk of a face f ∈ F(G). An incidence of the multigraph G is a pair (v, e), where v ∈ V (G), e ∈ E(G) and v is incident with e in G. Two distinct incidences (v1, e1) and (v2, e2) of G are facially adjacent if either e1= e2 or e1, e2are facially adjacent and either v1 = v2or v1≠v2and there is i ∈ {1, 2} such that eiis incident with both v1, v2. A facial incidence coloring of G assigns a color to each incidence of G in such a way that facially adjacent incidences get distinct colors. In this note we show that any embedded multigraph has a facial incidence coloring with seven colors. This bound is improved to six for several wide families of plane graphs and to four for plane triangulations.

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types

Let P and Q be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s -fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph with property P, all edges of color i induce a subgraph with property Q and vertices and incident edges have been assigned disjoint sets of colors. The minimum ratio of an r/s -fractional (P,Q)-total coloring of G is called fractional (P,Q)-total chromatic number χ″ƒ,P,Q(G) = r/ s . We show in this paper that χ″ƒ,P,Q of a graph G with o(V (G)) vertex orbits and o(E(G)) edge orbits can be found as a solution of a linear program with integer coefficients which consists only of o(V (G)) + o(E(G)) inequalities.

Let P and Q be additive and hereditary graph properties, r, s ∈ N, r ≥ s, and [ℤr]s be the set of all s-element subsets of ℤr. An (r, s)-fractional (P,Q)-total coloring of G is an assignment h : V (G) ∪ E(G) → [ℤr]s such that for each i ∈ ℤr the following holds: the vertices of G whose color sets contain color i induce a subgraph of G with property P, edges with color sets containing color i induce a subgraph of G with property Q, and the color sets of incident vertices and edges are disjoint. If each vertex and edge of G is colored with a set of s consecutive elements of ℤr we obtain an (r, s)-circular (P,Q)-total coloring of G. In this paper we present basic results on (r, s)-fractional/circular (P,Q)-total colorings. We introduce the fractional and circular (P,Q)-total chromatic number of a graph and we determine this number for complete graphs and some classes of additive and hereditary properties.

Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.