Questions tagged [graph-colouring]
The graph-colouring tag has no usage guidance.
8
questions
38
votes
6
answers
3k
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? ;...
- 6,001
17
votes
1
answer
1k
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 ...
- 439
17
votes
1
answer
710
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 ...
- 1,591
16
votes
0
answers
489
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 ...
- 6,470
15
votes
3
answers
2k
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 cubic ...
- 20.9k
8
votes
1
answer
2k
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 P4-...
- 1,453
7
votes
1
answer
448
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 ...
- 1,955
2
votes
4
answers
6k
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:
...
- 247