Mixed graph colorings

A mixed graphG contains both undirected edges and directed arcs. Ak-coloring ofG is an assignment to its vertices of integers not exceedingk (also called colors) so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number (G) of a mixed graph is the smallestk such thatG admits ak-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of (G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience.     

On coloring numbers of graph powers

The weak $r$-coloring numbers ${\mathrm{wcol}}_r\left(G\right)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $\mathrm{col}\left(G\right)$, and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs.Let $G^p$ denote the $p$th power of $G$. We show that, all integers $p>0$ and $\Delta \ge 3$ and graphs $G$ with $\Delta \left(G\right)\le \Delta$ satisfy $\mathrm{col}\left(G^p\right)\in O\left(p\cdot {\mathrm{wcol}}_{\lceil p∕2\rceil }\left(G\right){(\Delta -1)}^{\lfloor p∕2\rfloor }\right)$; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in $p$. For the square of graphs $G$, we also show that, if the maximum average degree $2k-2<\mathrm{mad}\left(G\right)\le 2k$, then $\mathrm{col}\left(G^2\right)\le (2k-1)\Delta \left(G\right)+2k+1$.     

On the oriented chromatic number of graphs with given excess

The excess of a graph G is defined as the minimum number of edges that must be deleted from G in order to get a forest. We prove that every graph with excess at most k has chromatic number at most and that this bound is tight. Moreover, we prove that the oriented chromatic number of any graph with excess k is at most k+3, except for graphs having excess 1 and containing a directed cycle on 5 vertices which have oriented chromatic number 5. This bound is tight for k?4.     

Minimum sum edge colorings of multicycles

In the minimum sum edge coloring problem, we aim to assign natural numbers to edges of a graph, so that adjacent edges receive different numbers, and the sum of the numbers assigned to the edges is minimum. The chromatic edge strength of a graph is the minimum number of colors required in a minimum sum edge coloring of this graph. We study the case of multicycles, defined as cycles with parallel edges, and give a closed-form expression for the chromatic edge strength of a multicycle, thereby extending a theorem due to Berge. It is shown that the minimum sum can be achieved with a number of colors equal to the chromatic index. We also propose simple algorithms for finding a minimum sum edge coloring of a multicycle. Finally, these results are generalized to a large family of minimum cost coloring problems.     

Consecutive colorings of graphs

In a simple graphG=(X.E) a positive integerc _i is associated with every nodei. We consider node colorings where nodei receives a setS(i) ofc _i consecutive colors andS(i)S(j)=Ø whenever nodesi andj are linked inG. Upper bounds on the minimum number of colors needed are derived. The case of perfect graphs is discussed.

---

Zusammenfassung In einem schlichten GraphenG=(X, E) gibt man jedem Knotenpunkti einen positiven ganzzahligen Wertc _i. Wir betrachten Färbungen der Knotenpunkte, bei denen jeder Knotenpunkti eine MengeS(i) vonc _i konsekutiven Farben erhält mitS(i)S(j)=Ø wenn die Kante [i.j] existiert. Obere Grenzen für die minimale Anzahl der Farben solcher Färbungen werden hergeleitet. Der Fall der perfekten Graphen wird auch kurz diskutiert.

     

Locally restricted colorings

We consider the following problem: given suitable integers χ and p, what is the smallest value ρ such that, for any graph G with chromatic number χ and any vertex coloring of G with at most χ+p colors, there is a vertex v such that at least χ different colors occur within distance ρ of v? Let ρ(χ,p) be this value; we show in particular that ρ(χ,p)?⌈p/2⌉+1 for all χ,p. We give the exact value of ρ when p=0 or χ?3, and (χ,p)=(4,1) or (4,2).     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

On local search for the generalized graph coloring problem

Given an edge-weighted graph and an integer k, the generalized graph coloring problem is the problem of partitioning the vertex set into k subsets so as to minimize the total weight of the edges that are included in a single subset. We recall a result on the equivalence between Karush-Kuhn-Tucker points for a quadratic programming formulation and local optima for the simple flip-neighborhood. We also show that the quality of local optima with respect to a large class of neighborhoods may be arbitrarily bad and that some local optima may be hard to find.     

Dual graph homomorphism functions

For any two graphs F and G, let hom(F,G) denote the number of homomorphisms F→G, that is, adjacency preserving maps V(F)→V(G) (graphs may have loops but no multiple edges). We characterize graph parameters f for which there exists a graph F such that f(G)=hom(F,G) for each graph G.The result may be considered as a certain dual of a characterization of graph parameters of the form hom(.,H), given by Freedman, Lovász and Schrijver [M. Freedman, L. Lovász, A. Schrijver, Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007) 37-51]. The conditions amount to the multiplicativity of f and to the positive semidefiniteness of certain matrices N(f,k).     

Remarks on the distribution of colors in Gallai colorings

A Gallai coloring of a complete graph $K_n$ is an edge coloring without triangles colored with three different colors. A sequence $e_1\ge \cdots \ge e_k$ of positive integers is an $(n,k)$-sequence if ${\sum }_{i=1}^k{e}_i=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. An $(n,k)$-sequence is a G-sequence if there is a Gallai coloring of $K_n$ with $k$ colors such that there are $e_i$ edges of color $i$ for all $i,1\le i\le k$. Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer $k\ge 3$ there exists an integer $g\left(k\right)$ such that every $(n,k)$-sequence is a G-sequence if and only if $n\ge g\left(k\right)$. They showed that $g\left(3\right)=5,g\left(4\right)=8$ and $2k-2\le g\left(k\right)\le 8k^2+1$.We show that $g\left(5\right)=10$ and give almost matching lower and upper bounds for $g\left(k\right)$ by showing that with suitable constants $\alpha ,\beta >0$, $\frac{\alpha k^{1.5}}{lnk}\le g\left(k\right)\le \beta k^{1.5}$ for all sufficiently large $k$.     

Hall number for list colorings of graphs: Extremal results

Given a graph G=(V,E) and sets L(v) of allowed colors for each v∈V, a list coloring of G is an assignment of colors φ(v) to the vertices, such that φ(v)∈L(v) for all v∈V and φ(u)≠φ(v) for all uv∈E. The choice number of G is the smallest natural number k admitting a list coloring for G whenever |L(v)|≥k holds for every vertex v. This concept has an interesting variant, called Hall number, where an obvious necessary condition for colorability is put as a restriction on the lists L(v). (On complete graphs, this condition is equivalent to the well-known one in Hall’s Marriage Theorem.) We prove that vertex deletion or edge insertion in a graph of order n>3 may make the Hall number decrease by as much as n−3. This estimate is tight for all n. Tightness is deduced from the upper bound that every graph of order n has Hall number at most n−2. We also characterize the cases of equality; for n≥6 these are precisely the graphs whose complements are K₂∪(n−2)K₁, P₄∪(n−4)K₁, and C₅∪(n−5)K₁. Our results completely solve a problem raised by Hilton, Johnson and Wantland [A.J.W. Hilton, P.D. Johnson, Jr., E. B. Wantland, The Hall number of a simple graph, Congr. Numer. 121 (1996), 161-182, Problem 7] in terms of the number of vertices, and strongly improve some estimates due to Hilton and Johnson [A.J.W. Hilton, P.D. Johnson, Jr., The Hall number, the Hall index, and the total Hall number of a graph, Discrete Appl. Math. 94 (1999), 227-245] as a function of maximum degree.     

Bicolored graph partitioning, or: gerrymandering at its worst

This study is motivated by an electoral application where we look into the following question: how much biased can the assignment of parliament seats be in a majority system under the effect of vicious gerrymandering when the two competing parties have the same electoral strength? To give a first theoretical answer to this question, we introduce a stylized combinatorial model, where the territory is represented by a rectangular grid graph, the vote outcome by a “balanced” red/blue node bicoloring and a district map by a connected partition of the grid whose components all have the same size. We constructively prove the existence in cycles and grid graphs of a balanced bicoloring and of two antagonist “partisan” district maps such that the discrepancy between their number of “red” (or “blue”) districts for that bicoloring is extremely large, in fact as large as allowed by color balance.     

A Branch-and-Cut algorithm for graph coloring

In this paper a Branch-and-Cut algorithm, based on a formulation previously introduced by us, is proposed for the Graph Coloring Problem. Since colors are indistinguishable in graph coloring, there may typically exist many different symmetrical colorings associated with a same number of colors. If solutions to an integer programming model of the problem exhibit that property, the Branch-and-Cut method tends to behave poorly even for small size graph coloring instances. Our model avoids, to certain extent, that bottleneck. Computational experience indicates that the results we obtain improve, in most cases, on those given by the well-known exact solution graph coloring algorithm Dsatur.     

The neighborhood complex of a random graph

For a graph G, the neighborhood complex N[G] is the simplicial complex having all subsets of vertices with a common neighbor as its faces. It is a well-known result of Lovász that if ‖N[G]‖ is k-connected, then the chromatic number of G is at least k+3.We prove that the connectivity of the neighborhood complex of a random graph is tightly concentrated, almost always between 1/2 and 2/3 of the expected clique number. We also show that the number of dimensions of nontrivial homology is almost always small, O(logd), compared to the expected dimension d of the complex itself.     

All countable monoids embed into the monoid of the infinite random graph

We prove that the full transformation monoid on a countably infinite set is isomorphic to a submonoid of , the endomorphism monoid of the infinite random graph R. Consequently, embeds each countable monoid, satisfies no nontrivial monoid identity, and has an undecidable universal theory.