Search

An incidencein a graph Gis a pair (v, e) where vis a vertex of Gand eis an edge of Gincident 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 vuis from the set {e, f}. An incidence coloringof Gis 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= e2or 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, r, s ∈ N, r ≥ s, and [ℤr]sbe 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]ssuch that for each i ∈ ℤrthe 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 ℤrwe 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.

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.

A sequence r1, r2, …, r2nsuch that ri=rn+ ifor all 1≤i≤nis called a repetition. A sequence Sis called non‐repetitiveif no block(i.e. subsequence of consecutive terms of S) is a repetition. Let Gbe a graph whose edges are colored. A trail is called non‐repetitiveif the sequence of colors of its edges is non‐repetitive. If Gis a plane graph, a facial non‐repetitive edge‐coloringof Gis an edge‐coloring such that any facial trail(i.e. a trail of consecutive edges on the boundary walk of a face) is non‐repetitive. We denote π′f(G) the minimum number of colors of a facial non‐repetitive edge‐coloring of G. In this article, we show that π′f(G)≤8 for any plane graph G. We also get better upper bounds for π′f(G) in the cases when Gis a tree, a plane triangulation, a simple 3‐connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 38–48, 2010

A face of an edge‐colored plane graph is called rainbowif the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbownessof G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor Hof G, where a bridge face factor Hof a plane graph Gis a spanning subgraph Hof Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009