On the Minimum Sum Coloring of P 4-Sparse Graphs

In this paper, we study the minimum sum coloring (MSC) problem on P ₄-sparse graphs. In the MSC problem, we aim to assign natural numbers to vertices of a graph such that adjacent vertices get different numbers, and the sum of the numbers assigned to the vertices is minimum. Based in the concept of maximal sequence associated with an optimal solution of the MSC problem of any graph, we show that there is a large sub-family of P ₄-sparse graphs for which the MSC problem can be solved in polynomial time. Moreover, we give a parameterized algorithm and a 2-approximation algorithm for the MSC problem on general P ₄-sparse graphs.     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

Coloring circle graphs

Circle graph is an intersection graph of chords of a circle. We denote the class of circle graphs by cir. In this paper we investigate the chromatic number of the circle graph as a function of the size of maximum clique $\omega =\omega (G)$. More precisely we investigate $f(k)=\max \{\chi (G)|G\in \text{CIR }\mathrm{\&}\omega (G)⩽k\}$. Kratochvíl and Kostochka showed that $f(k)⩽50\cdot 2^k-32k-64$. The best lower bound is by Kostochka and is $f(k)=\mathrm{\Omega }(k\log k)$. We improve the upper bound to $f(k)⩽21\cdot 2^k-24k-24$. We also present the bound $\chi (G)⩽\omega \cdot \log n$ which shows, that the circle graphs with small maximum clique and large chromatic number must have many vertices.     

Sum List Coloring Block Graphs

A graph is f-choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. We characterize f-choosable functions for block graphs (graphs in which each block is a clique, including trees and line graphs of trees). The sum choice number is the minimum over all choosable functions f of the sum of the sizes in f. The sum choice number of any graph is at most the number of vertices plus the number of edges. We show that this bound is tight for block graphs.Acknowledgments. Partially supported by a grant from the Reidler Foundation. The author would like to thank an anonymous referee for useful comments.     

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 of universal graphs

LetG be a graph andr a cardinal number. Extending the theorem of J. Folkman we show that if eitherr or clG are finite then there existsH with clH = clG andH (G) _r ¹ . Answering a question of A. Hajnal we show that countably universal graphU ₃ satisfiesU ₃ (U₃) _r ¹ for every finiter.     

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 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.     

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 planar graphs in parallel

We present NC algorithms for vertex and edge coloring planar graphs. The vertex coloring algorithm 5 colors any planar graph, and the edge coloring algorithm Δ edge colors planar graphs with Δ ≥ 23 (and Δ + 1 edge colors planar graphs with Δ < 23), where Δ is the maximum degree in the graph.     

Minimum broadcast graphs

Let $\text{K}$ be a class of finite algebras closed under subalgebras, homomorphic images and finite direct products. It is shown that $\text{K}$ is isomorphic to the class of bounded distributive lattices if and only if $\text{K}$ is generated by a lattice-primal algebra.     

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.     

Minimum K-hamiltonian graphs

We consider two new classes of graphs arising from reliability considerations in network design. We want to construct graphs with a minimum number of edges which remain Hamiltonian after k edges (or k vertices) have been removed. A simple construction is presented for the case when k is even. We show that it is minimum k-edge Hamiltonian. On the other hand, Chartrand and Kapoor previously proved that this class of graphs was also minimum k-vertex Hamiltonian. The case when k is large (odd or even) is also considered. Some results about directed graphs are also presented.     

Halin图的邻和可区别边染色与边权点染色

记[k]={1,2,…,k),称为颜色集.设φ:E(G)→[k]为图G的边集合到[k]的映射,令f(v)表示与顶点v关联的边的颜色的加和.如果对任意一条边uv∈E(G),都有φ(u)≠φ(v),f(u)≠f(v),则称φ为图G的邻和可区别[k]-边染色,k的最小值称为图G的邻和可区别边色数,记为ndi_Σ(G).若对任意一条边uv∈E(G),都有f(u)≠f(v),则称φ为图G的k-边权点染色,称图G是k-边权可染的.运用组合零点定理证明了对于最大度不等于4的Halin图有:ndi_∑(G)≤Δ(G)+2,并证明了任一Halin图是4-边权可染的.