The tag has no wiki summary.

learn more… | top users | synonyms (1)

6
votes
0answers
111 views

Is graph coloring complete for poly-APX?

Is the graph coloring problem complete for poly-APX under C-reductions (alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
5
votes
1answer
151 views

The Overfull conjecture in graph theory and $coNP$

I am not good at complexity, but got a possible relation between a plausible conjecture in graph theory and $coNP$. Graph $G$ is Class 1 if it can be edge colored with $\Delta(G)$ colors, otherwise ...
2
votes
1answer
85 views

For which graph classes the fractional chromatic index rounded up equals the chromatic index?

Let $\chi'_f(G)$ be the fractional chromatic index. For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$? Since $\chi'_f(G)$ is computable in polynomial time, solving this gives tractable ...
0
votes
0answers
122 views

An interesting class of colored graphs?

Let $G$ be a complete graph edge-colored with $k$ colors. We say that $G$ is Gallai-colored if no triangle is colored with three distinct colors. Fix a tuple of integers $c = (c_1,\ldots,c_k)$. We may ...
1
vote
0answers
79 views

Chromatic number of a graph where neighbourhood of each vertex is isomorphic

Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$, the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the ...
6
votes
2answers
664 views

Anti-chromatic number

What is the maximum number of colors that can be used for coloring the vertices of a given graph, with no isolated vertices, such that each vertex should share its color with at least one of its ...
5
votes
1answer
184 views

Chromatic number of planar graph with girth at least k

The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones. Girth is ...
7
votes
1answer
130 views

Chromatic number of G+v where G is a cograph

Cograph is a well-know graph that does not have induced $P_4$. My questions are about determining the chromatic number of graphs in the class cograph+v. Notations: Denote by $\chi(G)$ the chromatic ...
12
votes
3answers
511 views

Graph coloring minimizing the number of colors in every independent set

Is the following claim known? Claim: For any graph $G$ with $n$ vertices there exists a coloring of $G$ such that every independent set is colored by at most $O(\sqrt{n})$ colors.
7
votes
1answer
183 views

How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a ...
2
votes
1answer
64 views

Complexity of Haemers' minimum rank

In 1978 Willem H. Haemmers published "An upper bound on the Shannon capacity of a graph". Tims has a survey of more recent results his thesis. What is the computational complexity of computing ...
5
votes
1answer
115 views

Worst case ratio between minimum clique cover and maximum independent set

The maximum independent set problem gives a lower bound for the minimum clique cover problem. This is easy to see because given any clique cover together with an independent set, any two vertices ...
10
votes
2answers
414 views

Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs

I heard of a result in approximate graph coloring, but cannot find the source. The result is: For every constant $h$ there exists a sufficiently large $k$ such that coloring a $k$-colorable graph ...
-1
votes
1answer
769 views

Flood fill vs depth first search

Is the flood fill algorithm the same as depth first search? If not, how do they differ in complexity?
6
votes
2answers
335 views

Decision problem related to coloring

Given a $k$-colorable graph $G$ and vertices $u$ and $v$ of $G$, what is the complexity of deciding if every $k$-coloring of $G$ must assign the same color to both $u$ and $v$? It does not seem ...
17
votes
1answer
727 views

What is the complexity of this edge coloring problem?

Recently, I have encountered the following variant of edge coloring. Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying ...
11
votes
2answers
1k views

Small graph with gap between chromatic and vector chromatic number?

I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$. ($G$ has vector chromatic number $q$ if there is an assignment $x\colon V ...
12
votes
4answers
669 views

hardness of approximating the chromatic number in graphs with bounded degree

I am looking for hardness results on vertex coloring of graphs with bounded degree. Given a graph $G(V,E)$, we know that for any $\epsilon>0$, it's hard to approximate $\chi(G)$ within a factor ...
19
votes
5answers
890 views

Reasons for which a graph may be not $k$ colorable?

While reasoning a bit on this question, I've tried to identify all the different reasons for which a graph $G = (V_G,E_G)$ may fail to be $k$ colorable. These are the only 2 reasons that I was able to ...
13
votes
1answer
482 views

Why are perfect graphs called perfect?

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
3
votes
1answer
149 views

bounded outdegree bipartite spanners

Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties : $G'$ ...
4
votes
1answer
338 views

Path coloring in general graphs

Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors. We know that coloring a set of paths ...
11
votes
1answer
178 views

An improper planar coloring with monochromatic component size $\leq 2$

Let us relax the coloring a little bit, that is, we allow a small number of adjacent vertices to be assigned the same color. A monochromatic component is defined to be a connected component in the ...
24
votes
1answer
693 views

Coloring complexity of graphs

Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ ...
4
votes
1answer
195 views

Algorithms for Interval Coloring with Capacities and Demands

We are given a graph $G = (V,E)$, where each edge $e \in E$ has a capacity $c_e$. There are a set of $k$ requests $R_1,\ldots,R_k$. Request $R_i$ has a demand $d_i$, and has an interval $I_i = ...
5
votes
1answer
342 views

Razborov's Approximation methods

The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem. People in parameterized complexity theory strongly believe that ...
2
votes
3answers
738 views

Complexity of greedy coloring

I was looking at some heuristics for coloring and found this book on Google books: Graph Colorings By Marek Kubale They describe the Greedy algorithm as follows: ...
4
votes
1answer
225 views

Chromatic number of a particular graph

Assume I have a parametrized graph. The parameters are two integers $x$ and $y<x$. Let $S(x)=\{1, \ldots, x\}$. The vertices of the graph are all the subsets of $S(x)$ of size $y$. Two vertices ...
10
votes
1answer
258 views

Hardness of approximating fractional chromatic number on bounded degree graphs

Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
11
votes
2answers
473 views

Approximate graph colouring with a promised upper bound on maximum independent set

In my job the following problem arises: Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 ...
1
vote
0answers
81 views

Resources to get started on fractional graph coloring algorithms

I'm interested in using fractional graph coloring algorithms/solvers to solve a problem, where is a good place to start? I'm looking to find basic/introductory to state-of-the-art algorithms more ...
14
votes
0answers
382 views

Question on Products of Graphs

Let $S_{n}(G)$, $C_{n}(G)$, $T_{n}(G)$ be the $n$-fold Strong Product, Cartesian Product and Tensor Product of a graph $G$ on $|V|$ vertices. Let the chromatic number ($\chi(G)$) and the independence ...
6
votes
1answer
239 views

Parallel algorithms to color interval graphs

Several NP-hard graph problems get easy if we consider interval graphs. There is a greedy algorithm to color optimally an interval graph. Just sort the intervals according their left endpoints and ...
4
votes
1answer
692 views

Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?

Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number ...
4
votes
1answer
249 views

3 colorable graphs

I was trying to understand the underlying difficulty of coloring 3 colorable graphs with as least number of colors as possible. Though i am aware of hardness result of coloring it with 4 colors, i ...
6
votes
2answers
261 views

Hardness of additive approximation to Graph Coloring problem.

In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the ...
36
votes
17answers
3k views

Conjectures implying Four Color Theorem

Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are ...
0
votes
1answer
469 views

graph coloring with 3 colors

I'm searching for an algorithm that can calculate a suboptimal solution for: color a graph with 3 colors some vertices already have a color and can't be changed the edges have values and the ...
6
votes
1answer
247 views

An image coloring problem

I have a large collection of microscopy images of cell cultures. Each image consists of $10^{10} \times 10^{10}$ pixels. These images have been "segmented", meaning that their pixels have been ...
5
votes
3answers
283 views

Hardness of finding a graph coloring given the optimal number of colors

We know that graph coloring is NP-complete even in some special graph classes. On the other hand if someone tells you the exact value of the chromatic number of the input graph, is this problem ...
20
votes
2answers
974 views

Coloring Planar Graphs

Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can ...
16
votes
3answers
297 views

Is there a constant factor approximation algorithm for 2D rectangle coloring problem?

The problem we consider here is the extension of the well-known interval coloring problem. Instead of intervals we consider rectangles having sides parallel to axes. The objective is to color the ...
11
votes
2answers
432 views

Do Shift-chains have Property B?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$. For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$. A $k$-uniform hypergraph ...
35
votes
1answer
671 views

How many distinct colors are needed to lower-bound the choosability of a graph?

A graph is $k$-choosable (also known as $k$-list-colorable) if, for every function $f$ that maps vertices to sets of $k$ colors, there is a color assignment $c$ such that, for all vertices $v$, ...
12
votes
3answers
1k views

Complexity of edge coloring in planar graphs

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". What is the complexity of 3-edge coloring of ...
23
votes
3answers
866 views

When is relaxed counting hard?

Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some ...
0
votes
3answers
954 views

Is it possible to have a 4-coloring for a non-planar graph ? [closed]

I have been working on this thread http://cstheory.stackexchange.com/questions/791/grid-k-coloring-without-monochromatic-rectangles, and I am aware that the four color theorem implies that all planar ...
12
votes
1answer
328 views

Efficient algorithm for near-optimal edge-colourings of hypergraphs

Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring. Question. What efficient algorithms are ...
35
votes
6answers
2k views

Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ...