Search Results

You are looking at 1 - 3 of 3 items for

  • Author: Massimiliano Marangio x
Clear All Modify Search
Open access

Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók, Janka Oravcová and Roman Soták

Abstract

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.

Open access

Arnfried Kemnitz, Massimiliano Marangio and Margit Voigt

Abstract

Let G = (V,E) be a simple graph and for every edge e ∈ E let L(e) be a set (list) of available colors. The graph G is called L-edge colorable if there is a proper edge coloring c of G with c(e) ∈ L(e) for all e ∈ E. A function f : E → ℕ is called an edge choice function of G and G is said to be f-edge choosable if G is L-edge colorable for every list assignment L with |L(e)| = f(e) for all e ∈ E. Set size(f) = ∑e∈E f(e) and define the sum choice index χ′sc(G) as the minimum of size(f) over all edge choice functions f of G.

There exists a greedy coloring of the edges of G which leads to the upper bound χ′sc(G) ≤ 1/2 ∑v∈V d(v)2. A graph is called sec-greedy if its sum choice index equals this upper bound.

We present some general results on the sum choice index of graphs including a lower bound and we determine this index for several classes of graphs. Moreover, we present classes of sec-greedy graphs as well as all such graphs of order at most 5.

Open access

Arnfried Kemnitz, Massimiliano Marangio and Margit Voigt

Abstract

A (graph) property 𝒫 is a class of simple finite graphs closed under isomorphisms. In this paper we consider generalizations of sum list colorings of graphs with respect to properties 𝒫.

If to each vertex v of a graph G a list L(v) of colors is assigned, then in an (L, 𝒫)-coloring of G every vertex obtains a color from its list and the subgraphs of G induced by vertices of the same color are always in 𝒫. The 𝒫-sum choice number Xsc𝒫(G) of G is the minimum of the sum of all list sizes such that, for any assignment L of lists of colors with the given sizes, there is always an (L, 𝒫)-coloring of G.

We state some basic results on monotonicity, give upper bounds on the 𝒫-sum choice number of arbitrary graphs for several properties, and determine the 𝒫-sum choice number of specific classes of graphs, namely, of all complete graphs, stars, paths, cycles, and all graphs of order at most 4.