On bounds for the incidentor chromatic number of a directed weighted multigraph

An incidentor coloring of a directed weighted multigraph is called admissible if: (a) the incidentors adjoining the same vertex are colored by different colors; (b) the difference between the colors of the final and initial incidentors of each arc is at least the weight of this arc. The minimum number of colors necessary for an admissible coloring of all incidentors of a multigraph G is bounded above and below. The upper and lower bounds differ by ┌Δ/2┐ where Δ is the degree of G.     

Star number and star arboricity of a complete multigraph

Let G be a multigraph. The star number s(G) of G is the minimum number of stars needed to decompose the edges of G. The star arboricity sa(G) of G is the minimum number of star forests needed to decompose the edges of G. As usual λK _n denote the λ-fold complete graph on n vertices (i.e., the multigraph on n vertices such that there are λ edges between every pair of vertices). In this paper, we prove that for n ⩾ 2

Bounds for the incidentor chromatic number of a weighted undirected multigraph

A proper incidentor coloring of an undirected weighted multigraph is called admissible if the absolute value of the difference between the colors of the incidentors of each edge is at least the weight of this edge. The minimum number of colors necessary for an admissible incidentor coloring is called the incidentor chromatic number of the multigraph. The problem of finding this number is studied in the paper. The NP-hardness of this problem is proved for Δ colors. Some upper and lower bounds are found for the incidentor chromatic number.     

The edge chromatic number of a directed/mixed multigraph

We consider colorings of the directed and undirected edges of a mixed multigraph G by an ordered set of colors. We color each undirected edge in one color and each directed edge in two colors, such that the color of the first half of a directed edge is smaller than the color of the second half. The colors used at the same vertex are all different. A bound for the minimum number of colors needed for such colorings is obtained. In the case where G has only directed edges, we provide a polynomal algorithm for coloring G with a minimum number of colors. An unsolved problem is formulated. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 267–273, 1999     

On incidentor coloring in a partially directed multigraph

We present an algorithmically effective procedure for finding the incidentor chromatic number of a partially directed multigraph.     

On list incidentor coloring of a multigraph of degree 3

It is shown that if the number of colors in a list of each arc of a directed multigraph of degree 3 is at least the weight of this arc plus 3 then the incidentors of this multigraph can be colored according to these lists.     

On Vizing’s bound for the chromatic index of a multigraph

Two of the basic results on edge coloring are Vizing’s Theorem [V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25-30 (in Russian); V.G. Vizing, The chromatic class of a multigraph, Kibernetika (Kiev) 3 (1965) 29-39 (in Russian). English translation in Cybernetics 1 32-41], which states that the chromatic index χ^′(G) of a (multi)graph G with maximum degree Δ(G) and maximum multiplicity μ(G) satisfies Δ(G)≤χ^′(G)≤Δ(G)+μ(G), and Holyer’s Theorem [I. Holyer, The NP-completeness of edge-colouring, SIAM J. Comput. 10 (1981) 718-720], which states that the problem of determining the chromatic index of even a simple graph is NP-hard. Hence, a good characterization of those graphs for which Vizing’s upper bound is attained seems to be unlikely. On the other hand, Vizing noticed in the first two above-cited references that the upper bound cannot be attained if Δ(G)=2μ(G)+1≥5. In this paper we discuss the problem: For which values Δ,μ does there exist a graph G satisfying Δ(G)=Δ, μ(G)=μ, and χ^′(G)=Δ+μ.     

Multicoloring the incidentors of a weighted undirected multigraph

Under consideration are the undirected multigraphs with weighted edges. In multicoloring incidentors, to each incidentor there is assigned a multicolor; i.e., an interval of colors whose length is equal to the weight of the incidentor. A multicoloring is proper if the multicolors of every two adjacent or mated incidentors are disjoint. We give some lower and upper estimates for the minimal number of colors necessary for a proper multicoloring of all incidentors of a graph.     

On the edge-chromatic number of a graph

V.G. Vizing has shown that the edge-chromatic number of any graph with maximum vertex-degree ρ is equal to either ρ or ρ + 1. In this paper, we describe various ways of constructing graphs whose edge-chromatic number is ρ + 1 and formulate a conjecture about such graphs.     

On the cyclomatic number of a hypergraph

This note generalizes the notion of cyclomatic number (or cycle rank) from Graph Theory to Hypergraph Theory and links it up with the concept of planarity in hypergraphs which was recently introduced by R.P. Jones. Sharp bounds are obtained for the cyclomatic number of the planar hypergraphs and, further, it is shown that the upper bound is attainable if, and only if the hypergraph satisfies Krewera's condition.     

The total coloring of a multigraph with maximal degree 4

In this paper it is proved that every multigraph with maximal degree 4 has a total coloring in six colors.     

On the Roman domination number of a graph

A Roman dominating function of a graph G is a labeling f:V(G)?{0,1,2} such that every vertex with label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_v∈V(G)f(v) over such functions. A Roman dominating function of G of weight γ_R(G) is called a γ_R(G)-function. A Roman dominating function f:V?{0,1,2} can be represented by the ordered partition (V₀,V₁,V₂) of V, where V_i={v∈V∣f(v)=i}. Cockayne et al. [E.J. Cockayne, P.A. Dreyer, S.M. Hedetniemi, S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004) 11-22] posed the following question: What can we say about the minimum and maximum values of |V₀|,|V₁|,|V₂| for a γ_R-function f=(V₀,V₁,V₂) of a graph G? In this paper we first show that for any connected graph G of order n≥3, , where γ(G) is the domination number of G. Also we prove that for any γ_R-function f=(V₀,V₁,V₂) of a connected graph G of order n≥3, , and .     

Decomposition of a complete multigraph into simple paths: Nonbalanced handcuffed designs

The condition λv(v ? 1) ≡ 0 (mod 2m), v ? m + 1 is obviously necessary for the existence of an edge disjoint decomposition of a complete multigraph λK_v into isomorphic simple paths consisting of m edges each. This condition is proved here to be sufficient. The proof is also valid in some cases when the given paths are not necessarity of the same length.     

On the number of cylinders touching a ball

The following problem is due to W. Kuperberg. What is the maximum number of non-overlapping unit cylinders (a set in \(\mathbb{E}^3 \) consisting of points whose distance from some line does not exceed 1) that can be simultaneously tangent to a unit ball? In this paper we prove that this number is at most 8. It is conjectured that this number is 6.     

On the number of hexagons in a map

A lower bound is given for the number of hexagonal faces in a simple map on a closed surface whose graph is 3-connected depending on the numbers of i-gonal faces, i ≠ 6, and the genus of the surface.     

On the interval number of a chordal graph

The interval number of a (simple, undirected) graph G is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t real intervals. A chordal (or triangulated) graph is one with no induced cycles on 4 or more vertices. If G is chordal and has maximum clique size ω(G) = m, then i(G) ? [1 + o(1)]m/log₂ m and this result is best possible, even for split graphs (chordal graphs whose complement is also chordal).