Coloring of character graphs

In this paper, we study the character graph Δ(G) of a finite solvable group G. We prove that sum of the chromatic number of Δ(G) and the matching number of complement graph of Δ(G) is equal to the order of Δ(G). Also, we prove that when Δ(G) is not a block, the chromatic number of Δ(G) is equal to the clique number of Δ(G).     

Coloring graphs with crossings

We generalize the Five-Color Theorem by showing that it extends to graphs with two crossings. Furthermore, we show that if a graph has three crossings, but does not contain K₆ as a subgraph, then it is also 5-colorable. We also consider the question of whether the result can be extended to graphs with more crossings.     

Coloring edges of embedded graphs

In this paper, we prove that any graph G with maximum degree , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

Coloring graphs with stable cutsets

This paper proves that if a graph G has a stable cutset S such that no vertex of S lies on a hole, then G is k-colorable if and only if the G_iUS are k-colorable, where G_i are the components of G ? S and a hole is a chordless odd-length (≥5) circuit. This result shows that critical hole-free perfect graphs cannot contain stable cutsets.     

Coloring signed graphs using DFS

We show that depth first search can be used to give a proper coloring of connected signed graphs G using at most \(\Delta (G)\) colors, provided G is different from a balanced complete graph, a balanced cycle of odd length, and an unbalanced cycle of even length, thus giving a new, short proof to the generalization of Brooks’ theorem to signed graphs, first proved by Má?ajová, Raspaud, and ?koviera.     

Some universal graphs

It is shown that various classes of graphs have universal elements. In particular, for eachn the class of graphs omitting all paths of lengthn and the class of graphs omitting all circuits of length at leastn possess universal elements in all infinite powers. Research partially supported by Hungarian Science Research Fund No. 1805. Research partially supported by NSERC of Canada Grant #A8948.     

Coloring the Cartesian sum of graphs

For graphs G and H, let G⊕H denote their Cartesian sum. We investigate the chromatic number and the circular chromatic number for G⊕H. It has been proved that for any graphs G and H, . It has been conjectured that for any graphs G and H, . We confirm this conjecture for graphs G and H with special values of χ_c(G) and χ_c(H). These results improve previously known bounds on the corresponding coloring parameters for the Cartesian sum of graphs.     

Coloring some classes of mixed graphs

We consider the coloring problem for mixed graphs, that is, for graphs containing edges and arcs. A mixed coloring c is a coloring such that for every edge [x_i,x_j], c(x_i)≠c(x_j) and for every arc (x_p,x_q), c(x_p)<c(x_q). We will analyse the complexity status of this problem for some special classes of graphs.     

Coloring the cliques of line graphs

The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph.Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals $2$ is NP-complete. We deal with the CCHN of the graph itself as well.     

Coloring planar perfect graphs by decomposition

This paper describes a decomposition scheme for coloring perfect graphs. Based on this scheme, one need only concentrate on coloring highly connected (at least 3-connected) perfect graphs. This idea is illustrated on planar perfect graphs, which yields a straightforward coloring algorithm. We suspect that, under appropriate definition, highly connected perfect graphs might possess certain regular properties that are amenable to coloring algorithms. This research has been supported in part by National Science Foundation under grant ECS—8105989 to Northwestern University.     

Coloring graphs which have equibipartite complements

If G is a graph of order $2n \geq 4$ with an equibipartite complement, then G is Class 1 (i.e., the chromatic index of G is Δ (G)) if and only if G is not the union of two disjoint K_n's with n odd. Similarly if G is a graph of order 2n ≥ 6 whose complement G is equibipartite with bipartition (A, D), and if both G and B, the induced bipartite subgraph of G with bipartition (A, D), have a 1-factor, then G is Type 1 (i.e., the total chromatic number of G is Δ (G) + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 183–194, 1997     

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvátal, Trotter and the two senior authors proved that for any Δ there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph KN with N?Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Δ. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and edges, with N=⌈B^′n⌉ for some constant B^′ that depends only on Δ. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Δ is . Our approach is based on random graphs; in fact, we show that the classical Erd?s–Rényi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Δ.The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed.     

Coloring graphs from random lists of size 2

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n^1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n^1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n.     

Some remarks on universal graphs

LetΓ be a class of countable graphs, and let ℱ(Γ) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member ofΓ. Furthermore, letTΓ andHΓ denote the class of all subdivisions of graphs inΓ and the class of all graphs contracting to a member ofΓ, respectively. As the main result of this paper it is decided which of the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ),n≦ℵ₀, contain a universal element. In fact, for ℱ(TK ⁴)=ℱ(HK ⁴) a strongly universal graph is constructed, whereas for 5≦n≦ℵ₀ the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ) have no universal elements. Dedicated to Klaus Wagner on his 75^th birthday     

Coloring graphs from random lists of fixed size

Let G = G(n) be a graph on n vertices with maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list uniformly at random from all k‐subsets of a color set of size . Such a list assignment is called a random ‐list assignment. In this paper, we are interested in determining the asymptotic probability (as ) of the existence of a proper coloring ? of G, such that for every vertex v of G. We show, for all fixed k and growing n, that if , then the probability that G has such a proper coloring tends to 1 as . A similar result for complete graphs is also obtained: if and L is a random ‐list assignment for the complete graph K_n on n vertices, then the probability that K_n has a proper coloring with colors from the random lists tends to 1 as .Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 317‐327, 2014     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.